Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I constructed the automaton below using the assumption that the language described by the regular expression above only accepted the following strings:

Empty, aabab, babab, aaaabab, bbbabab etc

Initially, I assumed that abab would not be accepted. (Not sure about this) Can someone please confirm if I have it right or if the automaton is missing something?

Initial automaton: enter image description here

Fixed automaton: (Is this one correct?)

enter image description here

share|cite|improve this question
up vote 1 down vote accepted

The regular expression $(a^*+b^*)(ab)^*$ does include $abab$; in fact, it includes $(ab)^n$ for every $n\ge 0$. But your automaton is missing a great deal more than that. For instance, it doesn’t accept $aaa$ or $b$, both of which are in the language.

Your automaton accepts the empty word, every word of the form $a^nb(ab)^m$ with $n\ge 3$ and $m\ge 0$, and every word of the form $b^n(ab)^m$ with $n\ge 1$ and $m\ge 1$. A regular expression for that language is $\lambda+aaab(ab)^*+bb^*ab(ab)^*$.

Here’s a transition table for a DFA that works:

$$\begin{array}{c|c|c} \text{state}&a&b\\ \hline s_0&s_a&s_b\\ s_a&s_a&s_{ab}\\ s_b&s_{ba}&s_b\\ s_{ab}&s_{ba}&s_\infty\\ s_{ba}&s_\infty&s_{ab}\\ s_\infty&s_\infty&s_\infty \end{array}$$

State $s_0$ is the initial state, and all states are acceptor states except $s_{ba}$ and $s_\infty$.

share|cite|improve this answer
Ah, I just realised what I did...Thanks for clarifying about the abab. So i take it, the following will all be accepted then?: Empty, a,b,abab,aaa,bbb,aaabab,bbabab,aab,bab..and so on. – zeqof Oct 18 '12 at 21:40
@zeqof: Yes, every one of those is in the language. – Brian M. Scott Oct 18 '12 at 21:44
Thank you. I have updated the question with the automaton I just fixed. Does that one correctly recognise the language described in the regular expression? – zeqof Oct 18 '12 at 22:04
@zeqof: Yes, that looks as if it should work. In fact, if you combine the state at the top right and the state just to the left of the garbage state into a single state, you get my DFA. – Brian M. Scott Oct 18 '12 at 22:11
Thanks for your help. :) – zeqof Oct 18 '12 at 22:12

It seems your automato does not even accept $a$ (and also not $abab$ as you suspected). I guess all states apart from the far right ("in the middle of not the first $ab$") and the "error" state should be accepting.

Also, your automaton is not deterministic.

share|cite|improve this answer
Yes thanks...I just realised where I went wrong. Fixing it now – zeqof Oct 18 '12 at 21:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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