# 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! Sep 18, 2017 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? Sep 19, 2017 at 12:27
• Since Yuval spent time on an answer already, no. Just keep our reference material in mind for next time! Sep 19, 2017 at 13:07

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