Can CFGs generate all languages? Are they (PDAs) finite or 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, &quot;most&quot; 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.