Exercise with regular languages

[mathmari]

Hello!
I need some help at the following exercise:
The language L={l ε {a,b}*:the word l does not contain the subword bba} is regular.Which are the equivalence classes of the relation \approx_{L} ?
Also,which is the smallest(as for the number of states) deterministic automata
that recognize this language?

 

[Evgeny.Makarov]

Have you studied the theory around the Myhill–Nerode theorem? It may be easier to try building the automaton.

Hint: One equivalence class consists of words that contain bba.

 

[mathmari]

Hint: One equivalence class consists of words that contain bba.

Could you explain to me how to find the equivalence classes??

Why does one equivalence class consists of words that contain bba, since the language is L={l ε {a,b}*:the word l does not contain the subword bba} ??

 

[Evgeny.Makarov]

Why does one equivalence class consists of words that contain bba, since the language is L={l ε {a,b}*:the word l does not contain the subword bba} ?

The equivalence relation is defined not on $L$, but on $\{a, b\}^*$. Thus, even words that are not in $L$ form equivalence classes. If $w\notin L$, then $[w]\cap L=\emptyset$ where $[w]$ is the equivalence class of $w$. This is because $u\approx_L w$ implies $u\varepsilon\in L\iff w\varepsilon\in L$ and $w\varepsilon=w\notin L$ where $\varepsilon$ is the empty word. In other words, $L$ is the union of some classes, and unless $L=\{a,b\}^*$, the complement of $L$ is the union of the rest of the classes.

Could you explain to me how to find the equivalence classes?

I recommend building an automaton recognizing the language. Then classes are naturally associated with the states of the automaton (with a single state if the automaton is minimal or with a subset of states otherwise). In particular, if a word contains $bba$, then it is definitely not in the language. If an automaton has read $bba$, then it should be in a "sink" state, from which there is no path to an accepting state.

For another example, if an automaton reads $a$ in the initial state, it can stay in that state because reading $a$ does not lead to reading $bba$. In terms of $\approx_L$, $\varepsilon w=w\in L\iff aw\in L$. That is, $a\in[\varepsilon]$. On the other hand, if an automaton reads $b$ in the initial state, it should remember this fact by switching to a different state. Reading $ba$ in that new state is not the same as reading $ba$ in the initial state. Thus, $b\notin[\varepsilon]$ because $bba\in L\nLeftrightarrow ba\in L$.

 

[mathmari]

I recommend building an automaton recognizing the language. Then classes are naturally associated with the states of the automaton (with a single state if the automaton is minimal or with a subset of states otherwise). In particular, if a word contains $bba$, then it is definitely not in the language. If an automaton has read $bba$, then it should be in a "sink" state, from which there is no path to an accepting state.

For another example, if an automaton reads $a$ in the initial state, it can stay in that state because reading $a$ does not lead to reading $bba$. In terms of $\approx_L$, $\varepsilon w=w\in L\iff aw\in L$. That is, $a\in[\varepsilon]$. On the other hand, if an automaton reads $b$ in the initial state, it should remember this fact by switching to a different state. Reading $ba$ in that new state is not the same as reading $ba$ in the initial state. Thus, $b\notin[\varepsilon]$ because $bba\in L\nLeftrightarrow ba\in L$.

Is the automaton the following:

q_{0}\overset{a}{\rightarrow}q_{0}
q_{0}\overset{b}{\rightarrow}q_{1}
q_{1}\overset{a}{\rightarrow}q_{0}
q_{1}\overset{b}{\rightarrow}q_{2}
q_{2}\overset{a}{\rightarrow}q_{3}
q_{2}\overset{b}{\rightarrow}q_{0}
q_{3}\overset{a,b}{\rightarrow}q_{3}
Final states: q_{0},q_{1},q_{2}. ??

 

[Evgeny.Makarov]

In state $q_2$, symbol $b$ should lead again to $q_2$. Your current version accepts $bbba$, which is incorrect. Other than that, I agree.

 

[mathmari]

So, to find the equivalence classes do I have to find all the words that are created by the automaton?

 

[Evgeny.Makarov]

I am not sure what you mean by "created". If two words drive the automaton from the initial state to the same state, then they are equivalent. This is because whatever continuation you choose, the automaton will behave the same, i.e., the automaton will end up in the same state on each of the two words plus the continuation. And since the automaton accepts the language in question, it can't happen that one word plus continuation is in the language while the other word plus continuation is not in the language. And this is the definition of $\approx_L$.

 

[mathmari]

So are the equivalence classes those that consist of the word that contain:
1) a
2) b
3) bb
4) bba
?

 

[Evgeny.Makarov]

So are the equivalence classes those that consist of the word that contain:
1) a
2) b
3) bb
4) bba
?

Yes.

 

[mathmari]

Is building an automaton recognizing the language the only way to find the equivalence classes?

 

[Evgeny.Makarov]

In some sense, yes because equivalence classes are isomorphic to the minimal automaton in the following sense. For each class $[w]$ there is a state $q_w$ and for each symbol $a$ there is a transition from $q_w$ to $q_{wa}$. This is the content of the Myhill-Nerode theorem. In particular, the number of classes is finite iff the automaton accepting the language is finite and hence the language is regular. Every language has the corresponding equivalence relation and, if I am not mistaken, is accepted by a possibly infinite automaton, but regularity means finiteness.

 

[mathmari]

So, having found the equivalence classes first, that means that the automaton has so many states as the number the equivalence classes?

 

[Evgeny.Makarov]

Why don't you study the theorem? "The Myhill–Nerode theorem states that $L$ is regular if and only if $R_L$ has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing $L$ is equal to the number of equivalence classes in $R_L$."

 

[mathmari]

Ok! Thank you! Your answers were helpful! (Yes)