9
$\begingroup$

A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have multiple heads, each of which moves through the input from left-to-right, but not necessarily at the same place in the input as the others.

Let us define a finite state machine with $k$ heads as follows:

A k-head NFA is a tuple $(Q, \Sigma, \Delta, q_0, F)$, where:

  • As usual, $Q$ is a finite set of states, $\Sigma$ is a finite alphabet, $q_0$ is an initial state, and $F$ is a set of accepting states. Let $\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$ denote the set of characters including the empty string.

  • $\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$ is the transition relation: a transition $(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$ means that, if the machine is in state $p$, it may read in $(\sigma_1, \sigma_2, \ldots, \sigma_k)$ such that $\sigma_i$ is the next character for head $i$ (or $\varepsilon$ if that head does not move), and then move to state $q$.

A run of this kind of machine (any path starting from the start state and ending in an accepting state) results in not one string, but $k$ different strings (formed by concatenating the characters along the run). Then we say that the run is valid if the $k$ strings are identical.

The language of the machine is the set of strings $w$ such that there exists a valid run of the machine where the $k$ strings produced along that run are all equal to $w$.

Question: What is the class of languages recognized by such machines? Has it been studied?


A first observation is that such machines produce a class larger than the regular languages. For example, the language $$ \{a^n b^n \mid n \in \mathbb{N}\} $$ is recognized by the following $2$-head NFA with $3$ states: 2-head NFA example

(Here, an edge labeled with $\sigma_1 / \sigma_2$ denotes a transition of the form $(p, (\sigma_1, \sigma_2), q)$.)

However, a second observation is that not all context-free languages are recognized; for example, it seems that the Dyck language cannot be recognized by these $k$-head machines.

$\endgroup$
  • 2
    $\begingroup$ Looking a bit around I see multi-head automata being mentioned in arxiv.org/abs/0906.3051: their definition is about two-way automata, but they also define the one-way variant. Isn't there something helpful in that paper? or in its references, e.g., sciencedirect.com/science/article/pii/S0304397509006288 $\endgroup$ – a3nm Oct 4 at 17:15
  • 2
    $\begingroup$ Also note that they can recognize non CF languages: a 3 head DFA can recognize $a^n b^n c^n\#$; a good reference source: Markus Holzer and Martin Kutrib; Multi-Head Finite Automata: Characterizations, Concepts and Open Problems $\endgroup$ – Marzio De Biasi Oct 4 at 17:32
  • 2
    $\begingroup$ Thanks for the paper references -- this was just an idle curiosity and I had not checked out the literature. If no one else does, I will read some literature and respond with an answer which summarizes the known results. $\endgroup$ – 6005 Oct 4 at 17:51
5
$\begingroup$

This model is one of the standard models in automata theory and it has been examined by some researchers.

The references given in the first comment are very good starting points.

When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my knowledge, we do not have a similar exact characterization, but, we have certain incomparable results and some hierarchies based on the number of heads.

If you are interested in, I recommend you to check alternating, probabilistic, and quantum versions of multi-head automata, as well. Such models can be quite interesting even when using a single head, as the computation is split in into different paths, and then, in each path, the head may access different part of the inputs.

Some generic references:

Alternation

Probabilistic computation

Probabilistic and quantum computation

Related models: multi-counter automata and automata using pebble.

$\endgroup$

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.