1
$\begingroup$

For the expression (ab)*ba I came up with the following (very poorly drawn):

DFA

However, this was not the correct answer - apparently the solution requires five states. I don't understand why my DFA doesn't describe the expression. My interpretation of the expression is "ab any number of times, followed by ba". Is this correct?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
1
$\begingroup$

For something to be a DFA, it should have transitions from every state for every letter in the alphabet. Your alphabet is {$a, b$}, so every state should have a transition for $a$ as well as $b$, e.g., your state 2 does not have a transition for $a$. Complete your DFA and you'll get what is that 5th state that you are missing.

Improve this answer
$\endgroup$
1
$\begingroup$

Your solution is correct—but you've built an NFA, not a DFA.

The difference is that an NFA can have any number of transitions on a single symbol from a single state. Anything from zero upward.

A DFA needs to have exactly one transition for each symbol from each state. Right now you're missing several of those. The fifth state to add is a "failure state" that transitions only to itself; make all the missing transitions go to this failure state.

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.