DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?

Question

Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we still didn't make its DFA.

I am trying to make Deterministic Finite Automata (DFA) of this lang which is defined on alphabet={a,b} and all strings present in this language are either start or end on double letter i.e aa or bb. The RE is given in title.

I made a DFA by using Kleene Theorems but its pretty complex. How i can directly make a DFA.

Answer 1

The DFA starts by reading the first two characters. If they happen to be the same, then it goes to an accepting state and just stays there. Otherwise, it keeps track of the last two characters of the word being read, being in an accepting state whenever they are the same.

Instead of writing a state diagram, here are the Myhill–Nerode equivalence classes of your language (given as regular expressions), which can be converted into a DFA with the same number of states as the number of equivalence classes:

• $q_0$: $\epsilon$.
• $q_1$: $a$.
• $q_2$: $b$.
• $q_3$: $(aa+bb)(a+b)^*$.
• $q_4$: $(a+b)^*aa \setminus (aa+bb)(a+b)^*$.
• $q_5$: $(a+b)^*ab \setminus (aa+bb)(a+b)^*$.
• $q_6$: $(a+b)^*ba \setminus (aa+bb)(a+b)^*$.
• $q_7$: $(a+b)^*bb \setminus (aa+bb)(a+b)^*$.

The initial state is $q_0$, and the accepting states are $q_3,q_4,q_7$.

Here is the transition function: $$ \begin{array}{c|cccccccc} & q_0 & q_1 & q_2 & q_3 & q_4 & q_5 & q_6 & q_7 \\\hline a & q_1 & q_3 & q_6 & q_3 & q_4 & q_6 & q_4 & q_6 \\ b & q_2 & q_5 & q_3 & q_3 & q_5 & q_7 & q_5 & q_7 \end{array} $$

Answer 2

Taking apart the regex we notice that any word starting with $\texttt{aa}$ or $\texttt{bb}$ is accepted which can be expressed with the following (incomplete) FS:

The remaining accepted words must have to end with either $\texttt{aa}$ or $\texttt{bb}$, so you need to "store" a read $\texttt{a}$ (or $\texttt{b}$) and distinguish between the next symbol if it's the same or another one:

• if it's the same, then we accept the word
• if not we transition to the state where we already read the other character

Finally, if we have read a symbol twice then we can read as many symbols of the same type again and the word is still accepted. If we read another one, we restart in the state where we already read one symbol of that type:

We are now ready to assemble the final, finite state machine: