Nondeterministic finite automaton

a finite of states ${\displaystyle Q}$,

set

a finite set of ${\displaystyle \Sigma }$,

input symbols

a transition function ${\displaystyle \delta }$ : ${\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$,

an initial (or start) state ${\displaystyle q_{0}\in Q}$, and

a set of states ${\displaystyle F}$ distinguished as accepting (or final) states ${\displaystyle F\subseteq Q}$.

In terms of the "lucky-run" explanation, each path in the picture denotes a sequence of choices of ${\displaystyle M}$.

above

In terms of the "cloning" explanation, each vertical column shows all clones of ${\displaystyle M}$ at a given point in time, multiple arrows emanating from a node indicate cloning, a node without emanating arrows indicating the "death" of a clone.

a finite of states ${\displaystyle Q}$

set

a finite set of called the alphabet ${\displaystyle \Sigma }$

input symbols

a transition ${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)}$

function

an initial (or ) state ${\displaystyle q_{0}\in Q}$

start

a set of states ${\displaystyle F}$ distinguished as ${\displaystyle F\subseteq Q}$.

accepting (or final) states

Union (cf. picture); that is, if the language L₁ is accepted by some NFA A₁ and L₂ by some A₂, then an NFA A_u can be constructed that accepts the language L₁∪L₂.

Intersection; similarly, from A₁ and A₂ an NFA A_i can be constructed that accepts L₁∩L₂.

Concatenation

Negation; similarly, from A₁ an NFA A_n can be constructed that accepts Σ^*\L₁.

Kleene closure

Convert to the equivalent DFA. In some cases this may cause exponential blowup in the number of states.

[9]

Keep a of all states which the NFA might currently be in. On the consumption of an input symbol, unite the results of the transition function applied to all current states to get the set of next states; if ε-moves are allowed, include all states reachable by such a move (ε-closure). Each step requires at most s² computations, where s is the number of states of the NFA. On the consumption of the last input symbol, if one of the current states is a final state, the machine accepts the string. A string of length n can be processed in time O(ns²),^[7]: 153 and space O(s).

set data structure

Create multiple copies. For each n way decision, the NFA creates up to n−1 copies of the machine. Each will enter a separate state. If, upon consuming the last input symbol, at least one copy of the NFA is in the accepting state, the NFA will accept. (This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)

Explicitly propagate tokens through the transition structure of the NFA and match whenever a token reaches the final state. This is sometimes useful when the NFA should encode additional context about the events that triggered the transition. (For an implementation that uses this technique to keep track of object references have a look at Tracematches.)

[10]

One can solve in linear time the for NFA, i.e., check whether the language of a given NFA is empty. To do this, we can simply perform a depth-first search from the initial state and check if some final state can be reached.

emptiness problem

It is -complete to test, given an NFA, whether it is universal, i.e., if there is a string that it does not accept.^[11] As a consequence, the same is true of the inclusion problem, i.e., given two NFAs, is the language of one a subset of the language of the other.

PSPACE

Given as input an NFA A and an integer n, the of determining how many words of length n are accepted by A is intractable; it is #P-hard. In fact, this problem is complete (under parsimonious reductions) for the complexity class SpanL.^[12]

counting problem

Deterministic finite automaton

Two-way nondeterministic finite automaton

Pushdown automaton

Nondeterministic Turing machine

M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp. 115–125.

Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997.  0-534-94728-X. (see section 1.2: Nondeterminism, pp. 47–63.)

ISBN

John E. Hopcroft and Jeffrey D. Ullman, , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 2.)

Introduction to Automata Theory, Languages, and Computation