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

Question

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?

Answer 1

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

Answer 2

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.