1
$\begingroup$

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

2 Answers 2

0

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

  • 0
    @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.2012-10-18
0

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.

  • 0
    Yes thanks...I just realised where I went wrong. Fixing it now2012-10-18