Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?

Question

I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG).

I suspect that languages like $\text{L} = \{10,10100,101001000, \dots\}$ can not be generated by a CFG. I can not see that intuitively (heuristics will help me). I have seen PDAs to be finite state automata in some places, and infinite in the rest.

Can someone tell me the limitations of a CFG / PDA (if any) and whether or not $\text{L}$ can be generated by a PDA/CFG? Additionally, are PDAs infinite state automata?

Answer 1

Since each context-free language can be described by a grammar, there are only countably many context-free languages (over a fixed alphabet). Therefore, "most" languages are not context-free. Examples of particular languages which are not context-free abound. Your language $\{ 1010^210^3\cdots 10^n : n \geq 1 \}$ is one such example. It can be proved to be non-context-free using the pumping lemma, for example.

Push-down automata have finitely many states, but an infinite stack. Although the stack is infinite, it can only be accessed in very specific ways, and this severely limits the power of the automaton. If we replace the stack with a queue, or add a second stack, then the automaton becomes much more powerful – equivalent to a Turing machine. But even such automata can only accept countably many languages. In particular, they cannot accept uncomputable languages such as that of the halting problem, as shown by Turing.