# Understand the DFA: accepting or not accepting “aa” or “bb”

I want to discuss the strings accepted by couple of DFAs: DFA in Figure 1 has 3 final states. It looks like that it accepts both the substrings "aa" (q0q3q0q1) or "bb". So this is not I want. DFA in Figure 2 has one final state q0. Its good because it does not accept "aa" or "bb" but the problem is that it does not accept any string so its useless. DFA in figure 3 accept a, aba. It looks like that it can accept any number of "ab" but does it accept "aa" or "aaa"? Can the start state generate any number of 'a's to be accepted by the final state? I am not sure somebody please guide me.

Zulfi.

• How do you conclude that the first automaton accepts $aa$ and $bb$?? – J.-E. Pin Sep 23 '20 at 11:31

The first automaton is a bit complicated. The language it recognizes should be, in regular expression form, $$((ab)^\ast (ba)^\ast)^\ast (a + b + \varepsilon)$$ where $$\varepsilon$$ denotes the empty word. The second one, as you noted, has no edges returning to the only final state which also happens to be the initial state. Hence the language it recognizes is $$\{\varepsilon\}$$, but it surely is a complicated automaton for doing this.
The third automaton recognizes the language $$a(ba)^\ast$$. It does not accept any words containing substrings $$aa$$ or such as starting from any state, taking 2 consecutive $$a$$-transitions will land you in that bottom sink state from which the accepting state cannot be reached.
The fourth automaton is actually not a DFA but a NFA (but that makes no big difference). It recognizes the language $$a(baa^\ast)^\ast$$, which is different from the expression you gave as yours is missing the possibility for taking the loop from the accepting state through the initial state via $$b$$ and back to the accepting state via $$a$$. In particular, this loop shows that if the automaton accepts $$w$$, then it also accepts $$w(ba)^\ast$$.