I want to discuss the strings accepted by couple of DFAs:

Figure 1

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.

Figure 2

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.

Figure 3

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.

Somebody please guide me.


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

It is not clear if you actually want to construct an automaton for some language, however I can provide some help with understanding the given ones.

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$.

In general, analyzing the language recognized by some DFA boils down to finding the paths from the initial state to a final state and then accounting for loops along the way, which sometimes can be a bit confusing, but try to do this for the third and fourth automata yourself. I am sure that you will be able to understand them that way in no time :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.