1
$\begingroup$

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:

enter image description here

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – Raphael
    Commented Sep 18, 2017 at 20:37
  • $\begingroup$ @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? $\endgroup$
    – LeoColman
    Commented Sep 19, 2017 at 12:27
  • 1
    $\begingroup$ Since Yuval spent time on an answer already, no. Just keep our reference material in mind for next time! $\endgroup$
    – Raphael
    Commented Sep 19, 2017 at 13:07

1 Answer 1

Reset to default
1
$\begingroup$

Here's one possible solution:

DFA for $b(bb)^*(aa)^*$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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