Does there exist a universal pushdown automaton?

Question

Let $\Sigma$ be a fixed alphabet and let $PDA(\Sigma)$ be the set of all Push-Down-Automata (PDA's) having input alphabet $\Sigma$. Is there an alphabet $S$ and a function $f:PDA(\Sigma) \to S^∗$ such that the set $\{(f(A),w) : w \in L(A)\}$ is accepted by a non-deterministic push-down automaton? If not, is the answer positive if we replace PDA's with Finite Automata (keeping the universal recognizer a PDA)?

Answer 1

This is not possible, assuming $(f(A),w)$ means writing the code of $A$ and then writing input $w$. Context-free (and regular) languages have a pumping property, that is certain substrings can be repeated. I assume you have seen the concept. The length-bounds on the repeated parts are determined by the language you are interested in, and can be arbitrary large. The "universal PDA" on the other hand has its own fixed pumping constant that cannot match arbitrary large values in the coded languages. This argument however only works if we can enforce having to avoid pumping in the $f(A)$ part of the description. For regular languages that is not a big problem, for context-free we need a rather strong pumping result.

Sorry, no details here. Not enough space ....