# Regular Expression for {W | W contains an even number of As and an odd number of Bs, but doesn't contains AB}

While studying Automata at my University, I faced the following problem from SIPSER, M textbook:

Consider D = { w | w contains an even number of as and an odd number of bs and doesn't contains the chain ab}. Draw an DFA with 5 states that recognizes D and a Regular Expression that generated D.

I tried doing the following DFA:

With the Regular Expression b(bb)*(aa)*

And that seemed quite right for me, but for chains that goes like baab it should be refused, but it isn't.

I couldn't find a way to fix it without adding another state to the DFA.

How can it be done?

• Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! – Raphael Sep 18 '17 at 20:37
• @Raphael thanks for the linking. Perhaps I shoul've taken a look at this link before asking my question. It does have an answer tho, should I delete the question? – Kerooker Sep 19 '17 at 12:27
• Since Yuval spent time on an answer already, no. Just keep our reference material in mind for next time! – Raphael Sep 19 '17 at 13:07

Here's one possible solution:

(In fact, the words $b,bb,ba,baa,bab$ show that at least five states are needed, so this is the unique minimal DFA.)