Question about regular languages and finite automata

860 Views Asked by At

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the language of the automaton to be

$$L(M) = \{w \in \Sigma^* : \delta(q_0, w) \in F \}$$

If a language $L$ is merely contained in $L(M)$, $(L \subseteq L(M))$, do we say that $M$ accepts $L$, and thereby, $L$ is regular?

2

There are 2 best solutions below

0
On

No. For example, the monoid $\Sigma^*$ is a regular language, however certainly it contains subsets which are not regular.

0
On

Just to elaborate a little on Boris's answer: every language over a finite alphabet $\Sigma$ is a sublanguage of the regular language $\Sigma^*$, so the definition of regular languages would be almost useless (it would just mean 'language over a finite alphabet') if it included sublanguages of languages accepted by finite automata.

An automaton $M$ accepts exactly one language: the language $L(M)$ defined in your question, i.e. the language of all words accepted by $M$. If $L\subset L(M)$, then $M$ accepts $w$ for every word $w\in L$, but does not accept the language $L$ unless $L = L(M)$.