During recent research in a somewhat unrelated field (Spin Physics), I stumbled across a subclass of regular languages. The context of the research poses the question what the minimal power of the computational model would need to be in order to simulate the whole subclass.

As such I am interested in the question of what type of automaton is needed to simulate all DFAs. Let me define what I mean by this exactly:

Firstly Simulation: by simulate I mean the definition of simulation in the sense of the universal turning machine i.e. given a set of automata $\mathcal{A}$ acting on $\Sigma^*$, I define $T$ to simulate $\mathcal{A}$ if there exists a mapping $d: \mathcal{A} \rightarrow \Sigma^*$ such that $T(d(A)\circ x) = A(x)$ for all $A \in \mathcal{A}$ and $x \in \Sigma^*$.

I.e. given a description of an automaton $A$ and an input $x$ to said automaton $T$ produces the same result as $A$ would acting on $x$ directly.

Now secondly what do I mean by computational model?

Mostly just a certain type of automaton. I am of course aware that there exists a Turing machine that can complete this job (due to the existence of universal turning machines) and am fairly sure that an LBA should suffice as well, however, do there exist simpler examples e.g. PDAs and if not is there a neat argument why?

I am not necessarily looking for a concrete answer (though if someone can provide one that is of course well appreciated) but rather some pointers towards resources and the like that explore similar questions.

Thanks for any help!

  • 1
    $\begingroup$ Using a natural description of DFA by a transition table, such a simulation can be done by a logarithmic space machine in a straightforward way. $\endgroup$ May 4, 2023 at 13:45
  • 1
    $\begingroup$ A possible way to prove that a PDA $P$ cannot do the task: suppose that $P$ exists, then focus on DFAs on the unary language $\{1\}$ that recognize $1^{nk}$ (multiples of $k$) ; pick $k,n$ large enough ($k,n \gg $ pumping length $p$) and apply the pumping lemma (Ogden's lemma) on the $x$ part of the input $d(A)∘x$ pumping zero times, getting a string $x'$ such that $(n-1)k < |x'| = nk-p < nk $. $\endgroup$ May 4, 2023 at 14:16
  • 1
    $\begingroup$ In addition to above comments by Emil & Marzio: 1-way PDF with 2 stacks is universal and so too powerful. 1-way multi-counter or multi-head automata may not do such simulations. With an appropriate encoding of DFAs, 2-way DFAs with 3 heads should do such simulations. One head can read the input. Two heads can check the transitions and update them. My guess is that only two heads would not help. With such approach, certain "upper" and "lower" cases can be determined. $\endgroup$ May 4, 2023 at 15:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.