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

Question

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?)

Answer 1

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

Answer 2

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.