# DFA or NFA that accepts all words over the alphabet (a,b) that begins with ab and do not end with aa

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

$+ab(a+b)*(ab+bb+ba) 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?

• you are right... Feb 22 at 15:32

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

• 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? Feb 22 at 13:07
• Indeed, further singular cases can be added. 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.