Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

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

share|cite|improve this answer
This sounds plausible, but it contradicts Alberto's comment (for suitable values of "seems to"). – Rick Decker Oct 19 '12 at 1:17
Indeed, but it "seems" the Kudlek paper speaks of different types of encodings. First result is negative "Theorem 1: If encoding and decoding of specific finite or pushdown automata have to be achieved by DFST then there doesn’t exist a universal finite automaton, or 2-way finite automaton or pushdown automaton, simulating all specific finite automata." – Hendrik Jan Oct 19 '12 at 1:47
Sorry I did understand Kudlek's result finally but I didn't post any further comment. There is no universal PDA, but there does exist an automaton which is a composition of a 2-way PDA and a PDA that is capable of simulating all PDA's. The role of the 2-way PDA is restricted to "correctly reading" the string encoding of the PDA's. – Alberto Oct 20 '12 at 18:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.