# Does this PDA reject the string aabbcc?

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?

• Yes, this seems to be a sloppy solution. – Yuval Filmus Feb 10 '18 at 18:01
• @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? – Paradox Feb 10 '18 at 18:41
• Possibly. try to come up with an argument that explains why this machine works. – Yuval Filmus Feb 10 '18 at 20:17