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

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?

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.