This is the first question I'm asking here I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?

  • 1
    $\begingroup$ I believe there is a PDA with one step. The PDA essentially simulates a context-free grammar. The exact number of steps depends on your exact PDA model (for example, what is the acceptance criterion, does the stack get initialized, and so on). $\endgroup$ – Yuval Filmus Apr 6 at 18:42
  • 1
    $\begingroup$ What Yuval says. One state with empty stack acceptance (see wikipedia). Two states with final state acceptance (move to accept at the end). Three states if you are so unfortunate that you are taught using the Sipser book (which needs to put a bottom stack symbol first). $\endgroup$ – Hendrik Jan Apr 7 at 0:02

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.