# pushdown automata question

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.

• Hint: show that there are finitely many $100$-PDA over alphabet $\{a,b\}$. Jun 2 at 21:50
• @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. Jun 3 at 9:38