# Does there exist a universal pushdown automaton?

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)?

-
I found a paper that treats the argument: "Are there Universal Finite or Pushdown Automata?", by M. Kudlek et al. It seems the answer is yes but I did not yet completely understood the proof. –  Alberto Jul 12 '12 at 13:46
Do you have a citation for the paper? –  Rick Decker Oct 19 '12 at 1:14
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.