Design a (deterministic or nondeterministic) finite automaton A such that L(A) consists of all strings over the alphabet {a, b} that begin with ab and do not end with aa.

I have this question that is puzzling me and I cannot come to a conclusion

the best regex I could come up is the following


the empty string indicated with $ is accepted as it says all the words, then the compulsory ab concatenated with any word (a+b)* then also concatenated with all possible ending that are not aa. However this does not accept ab and or abb which should be accepted.

Maybe someone has better suggestions?


2 Answers 2


$\epsilon+ab(a+b)*(ab+bb+ba) + ab + abb$.

  • 1
    $\begingroup$ your case does not accept aba which should be part of the alphabet is $+ab(a+b)*(ab+bb+ba)+ab+abb+aba better then? $\endgroup$ Feb 22 at 13:07
  • $\begingroup$ Indeed, further singular cases can be added. $\endgroup$
    – Wuestenfux
    Feb 22 at 16:23

Personally, I've had a good time doing the DFA. Specifically:

  1. negate the DFA of $(a+b)^*aa$;
  2. do the DFA of $ab(a+b)^*$;
  3. do the product DFA of the previous two to intersect the languages.

You should end up with $3\times 4$ states to inspect. Three of them will form a graveyard subgraph in a somewhat obvious fashion. Other four will end up not being accessible. The resulting DFA has $6$ states and it's minimal, namely

\begin{array}[cc|c|c] &&\text{State}&a&b\\\hline \to& 1& 2&6\\\hline &2&6&3\\\hline \star&3&4&3\\\hline\star&4&5&3\\\hline&5&5&3\\\hline&6&6&6\end{array}

If you want a regular expression, I came up with $ab(a+b)^*(b+ba)+aba+ab$ off the top of my head.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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