9
$\begingroup$

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

  • 0
    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.2012-07-12
  • 0
    Do you have a citation for the paper?2012-10-19

1 Answers 1