2
$\begingroup$

Here, I read this:

For all CFL, there is a one-state PDA that recognizes this language.

What is the proof/idea behind this claim?

CFL: Context Free Languages PDA: Push Down Automaton

$\endgroup$
1
  • 1
    $\begingroup$ Check here. $\endgroup$
    – Nathaniel
    Feb 19 at 13:35

1 Answer 1

6
$\begingroup$

We have to be precise.

Each context-free language can be accepted by empty stack using a push-down automaton with a single state, or by final state and two states. (In the latter case we obviously need one accepting and one non-accepting state.)

The proof uses the equivalence between context-free grammars and push-down automata. Every CFG is equivalent to a PDA with a single state (and empty stack acceptance). Wikipedia mentions the expand-match construction which directly simulates the context-free derivation on the stack.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.