Design a DFA over alphabet (a,b) such that for all it's string no prefix contain two more a's than b's and two more b's than a's and the number of a's is equal to b's. Is it possible to design a DFA in such special cases of number of a's being equal to b's ,as it is not possible to make a DFA for the general case of a's being equal to b's. If yes ,why and how to recognize such cases.


To address your first question, this DFA will do the trick:

Correct DFA

The starting state is marked with an 'S' and it is also the only accepting state. Any string that has a prefix with 3 or more a's than it does b's will go out the right side and end up trapped in the trash state, and similarly, with b's to the left. Furthermore, it will only end up in the center if the number of a's equals the number of b's and the trash state is never visited.

The reason that we can find a DFA for this special case is that we really only need to be able to count between -3 and +3, which requires a finite amount of memory. The -3 and +3 come from the condition that prefixes have a and b counts within 2 of each other so if we ever hit -3 or +3 we can go to the trash state. In the general case, we may need to count arbitrarily high which requires infinite counting, not something a DFA can manage.

  • $\begingroup$ Looks like youve got two transitions out of S on i put a, making this an NFA? Was that intentional? A quick re-read suggests the left should be a mirror of the right, so the transitions on one side are flipped $\endgroup$ – D. Ben Knoble Mar 13 '20 at 15:07
  • $\begingroup$ @D.BenKnoble It was a mistake and I have now fixed it, thanks for spotting it! $\endgroup$ – Matt Werenski Mar 13 '20 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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