I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option.

NPDA are not very intuitive to me. The only solution I found online is: Solution

I don‘t really understand how it works and also I‘m not allowed to use final states. The only way an input is accepted is by emptying the Stack (how we do it at my university).

Thanks in advance!


First of all the answer you have provided is DPDA and not NPDA. "Z" denotes that your stack is empty, so you start by taking input i.e., "a" and keep storing them in your stack, as soon as "b" arrives you start removing one "a" for every "b" that arrives (b,a|Epsilon). Now their are two possibilities (i) m>n :- if so number of "b" are less than "a", so after all the "b" are computed only "E" will be left in the string so we reach the final state i.e., (E,a|a) (ii) n>m:- in this case all the "a"s will be removed so only "Z" will remain in the stack, so in this case this will be the final state i.e., (b,Z|Z)

Hope this will help.

| cite | improve this answer | |

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.