I've been given a solution, included below and I do not see how it would reject a string where i=j.

The example given should reject an input string such as aabbcc where there are an equal number of a's an b's, so i=j, however I don't see how it would reject it. Wouldn't it just push 2 a's, transition to state 2, pop 2 a's, epsilon transition to state 4, read in the two c's without popping or pushing and then accept? Is the given solution wrong or am I missing something?

enter image description here enter image description here

  • $\begingroup$ Yes, this seems to be a sloppy solution. $\endgroup$ – Yuval Filmus Feb 10 '18 at 18:01
  • $\begingroup$ @YuvalFilmus Could it be fixed by changing the epsilon transition from 2 to 4 into $\epsilon ; \epsilon / B \epsilon$? So that the top transition to 4 handles when j < i and the bottom transitions handle when j > i? $\endgroup$ – Paradox Feb 10 '18 at 18:41
  • $\begingroup$ Possibly. try to come up with an argument that explains why this machine works. $\endgroup$ – Yuval Filmus Feb 10 '18 at 20:17

Your Answer

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

Browse other questions tagged or ask your own question.