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?)
Best Answer
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$.