0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hint: show that there are finitely many $100$-PDA over alphabet $\{a,b\}$. $\endgroup$
    – Nathaniel
    Commented Jun 2, 2021 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$
    – Hendrik Jan
    Commented Jun 3, 2021 at 9:38

0

Reset to default

Your Answer

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