We define a new model: A "100-PDA" is a pushdown automaton with at most 100 states and with at most 100 symbols in the stack alphabet. Prove or disprove the following statement: "There exist infinitely many context-free languages on the alphabet {a,b} which cannot be recognized by any 100-PDA."

I haven't been able to come-up with much to prove this but I have a feeling that this machine can't differentiate between more than 100^2 numbers so maybe language of strings of length more than 100^2 is something it cant recognize.

  • 1
    $\begingroup$ Hint: show that there are finitely many $100$-PDA over alphabet $\{a,b\}$. $\endgroup$
    – Nathaniel
    Jun 2 at 21:50
  • $\begingroup$ @Nathaniel That was my initial reaction too. But I now think there are infinitely many 100-PDA. There is no bound on the number of symbols that can be pushed on the stack in a single instruction. $\endgroup$ Jun 3 at 9:38

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.