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$
$\endgroup$
2
-
$\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$– AlbertoJul 12, 2012 at 13:46
-
$\begingroup$ Do you have a citation for the paper? $\endgroup$– Rick DeckerOct 19, 2012 at 1:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$ Oct 19, 2012 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$ Oct 19, 2012 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$– AlbertoOct 20, 2012 at 18:46