Related models: multi-counter automata and automata using pebble. Turing Machines with Sublogarithmic Space.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. shtein distance, where it is allowed to delete a character from the.
Finite state automata discard pdf#
If you are interested in, I recommend you to check alternating, probabilistic, and quantum versions of multi-head automata, as well. PDF This paper presents an alternative way to use finite-state automata in order. 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. When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. The references given in the first comment are very good starting points. A DFA can be represented by a 5-tuple (Q,, , q 0, F. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton. Hence, it is called Deterministic Automaton. This model is one of the standard models in automata theory and it has been examined by some researchers. In DFA, for each input symbol, one can determine the state to which the machine will move. 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. (Here, an edge labeled with $\sigma_1 / \sigma_2$ denotes a transition of the form $(p, (\sigma_1, \sigma_2), q)$.) Is recognized by the following $2$-head NFA with $3$ states: Discarding these degenerate cases, it can. Question: What is the class of languages recognized by such machines? Has it been studied?Ī first observation is that such machines produce a class larger than the regular languages. between probabilistic finite-state automata and other well-known devices that generate strings like hidden. 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$. Then we say that the run is valid if the $k$ strings are identical. $\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$.Ī 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). Let $\Sigma_\varepsilon := \Sigma \cup \$ denote the set of characters including the empty string. Let us define a finite state machine with $k$ heads as follows:Ī k-head NFA is a tuple $(Q, \Sigma, \Delta, q_0, F)$, where:Īs 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.
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. I am looking for an algorithm to mark useful states, or remove useless states, that is not recursive (to prevent stack overflow, since I am looking at FAs with millions of states) and as efficient as possible.A DFA or NFA reads through an input string with a single head, moving left-to-right. But if you loop in decreasing order of $i$ shuffling found good states immediately into $G$, a single loop would suffice.īut this may lead to other degenerate situations (I am guessing).
In a degenerate automaton containing transitions $a_0\to a_1 \to\dots\to a_n\to f$ where $f$ is a single final state and an additional transition $a_n\to u$ such that $u$ is useless, there would be around $n$ loops if you always loop over the $a_i$ in the order of $i$. The number of loops checking $\Omega \setminus G$ is limited by the depth.
Repeat until nothing is added to $G$ any more.Ī straightforward implementation mimicking the above, however, can be quite costly, looping over states and transitions over and over again. Check all states $\Omega\setminus G$ for those that have a transition to a state in $G$ and add them to $G$. Theoretically, the algorithm to determine the useful states is trivial: Let $G$ be the set of good (useful) states and let $\Omega$ be the set of all states. A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state.
0 kommentar(er)
