<p>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.</p>
<p>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:</p>
<p>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 <span class="math-container">$\mathcal{A}$</span> acting on <span class="math-container">$\Sigma^*$</span>, I define <span class="math-container">$T$</span> to simulate <span class="math-container">$\mathcal{A}$</span> if there exists a mapping <span class="math-container">$d: \mathcal{A} \rightarrow \Sigma^*$</span>  such that
<span class="math-container">$T(d(A)\circ x) = A(x)$</span> for all <span class="math-container">$A \in \mathcal{A}$</span> and <span class="math-container">$x \in \Sigma^*$</span>.</p>
<p>I.e. given a description of an automaton <span class="math-container">$A$</span> and an input <span class="math-container">$x$</span> to said automaton <span class="math-container">$T$</span> produces the same result as <span class="math-container">$A$</span> would acting on <span class="math-container">$x$</span> directly.</p>
<p>Now secondly what do I mean by computational model?</p>
<p>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?</p>
<p>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.</p>
<p>Thanks for any help!</p>

CC BY-SA 4.0
2023-05-04T13:45:34.243Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-05-04T14:16:00.793Z
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 $.
Marzio De Biasi
CC BY-SA 4.0
2023-05-04T15:38:21.223Z
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.
Abuzer Yakaryilmaz
<automata-theory><dfa><universal-turing-machines>
What is the Simplest type of automaton that can simulate all DFAs?
Thomas Tappeiner
# What is the Simplest type of automaton that can simulate all DFAs?

(Asked by: username_0 on 2023-05-04)

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!

**Tags:** automata-theory, dfa, universal-turing-machines

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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 $.  
> **username_3**: 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.  

---

## 0 answers

