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:
(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.
