So i saw this statement in a book but it had no proof

is this even true? because i cannot come up with any idea that can make every CFL into a 2 state NPDA! how is that even possible?!

also if this is not true, then what about 3 states? can we make a 3 state NPDA for every CFL?


Yes, it's possible to construct NPDA having exactly 2 states for any CFG.

If you know how to construct NPDA having 3 states(q0, q1, q2) for given CFL(which can be found in some book on formal languages) then follow the given procedure to construct NPDA having exactly 2 states.

1) Instead of having (e, z, Sz) transition from q0 to q1, add transition (e, z, Sz') from q1 to q1 only.

2) Now replace transition from q1 to q2 which is labelled as (e, z, z) with (e, z', z).

3) Now make q1 the start state and remove state q0.

You got NPDA with exactly 2 states.

  • $\begingroup$ This doesn't quite answer the questino. Moreover, I have a hard time following your procedure. $\endgroup$ – Yuval Filmus Mar 12 at 11:54

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.