# For the regular expression, (a* + b*) . (a.b)* , does the following automaton recognise the language it describes?

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:

Fixed automaton: (Is this one correct?)

-

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

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

-
Yes thanks...I just realised where I went wrong. Fixing it now – zeqof Oct 18 '12 at 21:40