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

  • $\begingroup$ 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. $\endgroup$ – Alberto Jul 12 '12 at 13:46
  • $\begingroup$ Do you have a citation for the paper? $\endgroup$ – 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 ....

  • $\begingroup$ This sounds plausible, but it contradicts Alberto's comment (for suitable values of "seems to"). $\endgroup$ – Rick Decker Oct 19 '12 at 1:17
  • $\begingroup$ 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." $\endgroup$ – Hendrik Jan Oct 19 '12 at 1:47
  • 2
    $\begingroup$ 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. $\endgroup$ – Alberto Oct 20 '12 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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