![Relatively small NFA](https://upload.wikimedia.org/wikipedia/commons/5/59/Relatively_small_NFA.svg)
In
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
, a
finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
is called a
deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
(DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state transition.
A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is ''not'' a DFA, but not in this article.
Using the
subset construction algorithm
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same f ...
, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
.
Like DFAs, NFAs only recognize
regular languages
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
.
NFAs were introduced in 1959 by
Michael O. Rabin
Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award.
Biography Early life and education
Rabin was born in 1931 in ...
and
Dana Scott
Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, Ca ...
, who also showed their equivalence to DFAs. NFAs are used in the implementation of
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
s:
Thompson's construction
In computer science, Thompson's construction algorithm, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to ...
is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely,
Kleene's algorithm In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given nondeterministic finite automaton (NFA) into a regular expression.
Together with other conversion algorithms, it establishes the equival ...
can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton).
NFAs have been generalized in multiple ways, e.g.,
nondeterministic finite automata with ε-moves,
finite-state transducer
A finite-state transducer (FST) is a finite-state machine with two memory ''tapes'', following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. ...
s,
pushdown automata
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is
a type of automaton that employs a stack.
Pushdown automata are used in theories about what can be computed by machines. They are more capab ...
,
alternating automata,
ω-automata, and
probabilistic automata
In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the nondeterministic finite automaton; it includes the probability of a given transition into the finite state machine, transition function, turning it int ...
.
Besides the DFAs, other known special cases of NFAs
are
unambiguous finite automata (UFA)
and
self-verifying finite automata (SVFA).
Informal introduction
There are two ways to describe the behavior of an NFA, and both of them are equivalent. The first way makes use of the
nondeterminism
Nondeterminism or nondeterministic may refer to:
Computer science
*Nondeterministic programming
*Nondeterministic algorithm
*Nondeterministic model of computation
**Nondeterministic finite automaton
**Nondeterministic Turing machine
*Indeterminacy ...
in the name of an NFA. For each input symbol, the NFA transitions to a new state until all input symbols have been consumed. In each step, the automaton nondeterministically "chooses" one of the applicable transitions. If there exists at least one "lucky run", i.e. some sequence of choices leading to an accepting state after completely consuming the input, it is accepted. Otherwise, i.e. if no choice sequence at all can consume all the input and lead to an accepting state, the input is rejected.
In the second way, the NFA consumes a string of input symbols, one by one. In each step, whenever two or more transitions are applicable, it "clones" itself into appropriately many copies, each one following a different transition. If no transition is applicable, the current copy is in a dead end, and it "dies". If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected.
Formal definition
For a more elementary introduction of the formal definition see
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
.
Automaton
An ''NFA'' is represented formally by a
5-tuple,
, consisting of
* a finite
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of states
.
* a finite set of
input symbol
In formal language theory, an alphabet is a non-empty set of symbols/glyphs, typically thought of as representing letters, characters, or digits but among other possibilities the "symbols" could also be a set of phonemes (sound units). Alphabets in ...
s
.
* a transition function
:
.
* an ''initial'' (or ''start'') state
.
* a set of states
distinguished as ''accepting'' (or ''final'') ''states''
.
Here,
denotes the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of
.
Recognized language
Given an NFA
, its recognized language is denoted by
, and is defined as the set of all strings over the alphabet
that are accepted by
.
Loosely corresponding to the
above informal explanations, there are several equivalent formal definitions of a string
being accepted by
:
*
is accepted if a sequence of states,
, exists in
such that:
*#
*#
, for
*#
.
:In words, the first condition says that the machine starts in the start state
. The second condition says that given each character of string
, the machine will transition from state to state according to the transition function
. The last condition says that the machine accepts
if the last input of
causes the machine to halt in one of the accepting states. In order for
to be accepted by
, it is not required that every state sequence ends in an accepting state, it is sufficient if one does. Otherwise, ''i.e.'' if it is impossible at all to get from
to a state from
by following
, it is said that the automaton ''rejects'' the string. The set of strings
accepts is the
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
''recognized'' by
and this language is denoted by
.
*Alternatively,
is accepted if
, where
is defined
recursively
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
by:
*#
where
is the empty string, and
*#
for all
.
:In words,
is the set of all states reachable from state
by consuming the string
. The string
is accepted if some accepting state in
can be reached from the start state
by consuming
.
Initial state
The above automaton definition uses a ''single initial state'', which is not necessary. Sometimes, NFAs are defined with a set of initial states. There is an easy construction that translates an NFA with multiple initial states to an NFA with a single initial state, which provides a convenient notation.
Example
The following automaton
, with a binary alphabet, determines if the input ends with a 1.
Let
where
the transition function
can be defined by this
state transition table
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
(cf. upper left picture):
Since the set
contains more than one state,
is nondeterministic.
The language of
can be described by the
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
given by the
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
(0, 1)*1
.
All possible state sequences for the input string "1011" are shown in the lower picture.
The string is accepted by
since one state sequence satisfies the above definition; it doesn't matter that other sequences fail to do so.
The picture can be interpreted in a couple of ways:
* In terms of the
above "lucky-run" explanation, each path in the picture denotes a sequence of choices of
.
* In terms of the "cloning" explanation, each vertical column shows all clones of
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.
The feasibility to read the same picture in two ways also indicates the equivalence of both above explanations.
* Considering the first of the
above formal definitions, "1011" is accepted since when reading it
may traverse the state sequence
, which satisfies conditions 1 to 3.
* Concerning the second formal definition, bottom-up computation shows that
, hence
, hence
, hence
, and hence
; since that set is not disjoint from
, the string "1011" is accepted.
In contrast, the string "10" is rejected by
(all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state,
, by reading the final 0 symbol. While
can be reached after consuming the initial "1", this does not mean that the input "10" is accepted; rather, it means that an input string "1" would be accepted.
Equivalence to DFA
A
deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
(DFA) can be seen as a special kind of NFA, in which for each state and symbol, the transition function has exactly one state. Thus, it is clear that every
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
that can be recognized by a DFA can be recognized by an NFA.
Conversely, for each NFA, there is a DFA such that it recognizes the same formal language. The DFA can be constructed using the
powerset construction
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same f ...
.
This result shows that NFAs, despite their additional flexibility, are unable to recognize languages that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has ''n'' states, the resulting DFA may have up to
states, which sometimes makes the construction impractical for large NFAs.
NFA with ε-moves
Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA. In this kind of automaton, the transition function is additionally defined on the
empty string
In formal language theory, the empty string, or empty word, is the unique string of length zero.
Formal theory
Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
ε. A transition without consuming an input symbol is called an ε-transition and is represented in state diagrams by an arrow labeled "ε". ε-transitions provide a convenient way of modeling systems whose current states are not precisely known: i.e., if we are modeling a system and it is not clear whether the current state (after processing some input string) should be q or q', then we can add an ε-transition between these two states, thus putting the automaton in both states simultaneously.
Formal definition
An ''NFA-ε'' is represented formally by a
5-tuple,
, consisting of
* a finite
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of
states
* a finite set of
input symbol
In formal language theory, an alphabet is a non-empty set of symbols/glyphs, typically thought of as representing letters, characters, or digits but among other possibilities the "symbols" could also be a set of phonemes (sound units). Alphabets in ...
s called the
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
* a transition
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
* an ''initial'' (or
''start'') state
* a set of states
distinguished as
''accepting'' (or ''final'') ''states'' .
Here,
denotes the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of
and ε denotes empty string.
ε-closure of a state or set of states
For a state
, let
denote the set of states that are reachable from
by following ε-transitions in the transition function
, i.e.,
if there is a sequence of states
such that
*
,
*
for each
, and
*
.
is known as the epsilon closure, (also ε-closure) of
.
The ε-closure of a set
of states of an NFA is defined as the set of states reachable from any state in
following ε-transitions. Formally, for
, define
.
Extended transition function
Similar to NFA without ε-moves, the transition function
of an NFA-ε can be extended to strings.
Informally,
denotes the set of all states the automaton may have reached when starting in state
and reading the string
The function
can be defined recursively as follows.
*
, for each state
and where
denotes the epsilon closure;
:''Informally:'' Reading the empty string may drive the automaton from state
to any state of the epsilon closure of
*
for each state
each string
and each symbol
:''Informally:'' Reading the string
may drive the automaton from state
to any state
in the recursively computed set
; after that, reading the symbol
may drive it from
to any state in the epsilon closure of
The automaton is said to accept a string
if
:
that is, if reading
may drive the automaton from its start state
to some accepting state in
Example
Let
be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s. Note that 0 occurrences is an even number of occurrences as well.
In formal notation, let
where
the transition relation
can be defined by this
state transition table
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
:
can be viewed as the union of two
DFAs: one with states
and the other with states
.
The language of
can be described by the
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
given by this
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
.
We define
using ε-moves but
can be defined without using ε-moves.
Equivalence to NFA
To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε, so it remains to show for every NFA-ε, there exists an equivalent NFA.
Given an NFA with epsilon moves
define an NFA
where
:
and
:
for each state
and each symbol
using the extended transition function
defined above.
One has to distinguish the transition functions of
and
viz.
and
and their extensions to strings,
and
respectively.
By construction,
has no ε-transitions.
One can prove that
for each string
, by induction on the length of
Based on this, one can show that
if, and only if,
for each string
* If
this follows from the definition of
* Otherwise, let
with
and
:From
and
we have
we still have to show the "
" direction.
:*If
contains a state in
then
contains the same state, which lies in
.
:*If
contains
and
then
also contains a state in
viz.
:*If
contains
and
then must be in
Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.
Closure properties
![Thompson-or](https://upload.wikimedia.org/wikipedia/commons/2/25/Thompson-or.svg)
The set of languages recognized by NFAs is
closed under
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but n ...
the following operations. These closure operations are used in
Thompson's construction algorithm
In computer science, Thompson's construction algorithm, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to ...
, which constructs an NFA from any
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
. They can also be used to prove that NFAs recognize exactly the
regular languages
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
.
*Union (cf. picture); that is, if the language ''L''
1 is accepted by some NFA ''A''
1 and ''L''
2 by some ''A''
2, then an NFA ''A''
u can be constructed that accepts the language ''L''
1∪''L''
2.
*Intersection; similarly, from ''A''
1 and ''A''
2 an NFA ''A''
i can be constructed that accepts ''L''
1∩''L''
2.
*Concatenation
*Negation; similarly, from ''A''
1 an NFA ''A''
n can be constructed that accepts Σ
*\''L''
1.
*
Kleene closure
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
Since NFAs are equivalent to nondeterministic finite automaton with ε-moves (NFA-ε), the above closures are proved using closure properties of NFA-ε.
Properties
The machine starts in the specified initial state and reads in a string of symbols from its
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
. The automaton uses the
state transition function
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
Δ to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in". If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.
The set of all strings accepted by an NFA is the language the NFA accepts. This language is a
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
.
For every NFA a
deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
(DFA) can be found that accepts the same language. Therefore, it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the
powerset construction
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same f ...
, which may lead to an exponential rise in the number of necessary states. For a formal proof of the powerset construction, please see the
Powerset construction
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same f ...
article.
Implementation
There are many ways to implement a NFA:
* Convert to the equivalent DFA. In some cases this may cause exponential blowup in the number of states.
* Keep a
set data structure
In computer science, a set is an abstract data type that can store unique values, without any particular order. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrievin ...
of all states which the NFA might currently be in. On the consumption of an input symbol,
unite
Unite may refer to:
Arts, entertainment, and media Music Albums
* ''Unite'' (A Friend in London album), 2013 album by Danish band A Friend in London
* ''Unite'' (Kool & the Gang album), 1993
* ''Unite'' (The O.C. Supertones album), 2005
Songs ...
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''
2 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
2),
and space ''O''(''s'').
* Create multiple copies. For each n way decision, the NFA creates up to
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.)
* It is
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
-complete to test, given an NFA, whether it is ''universal'', i.e., if there is a string that it does not accept.
[Historically shown in: For a modern presentation, se]
/ref> 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.
Application of NFA
NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa. The establishment of such equivalence is important and useful. It is useful because constructing an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language. It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation
In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., a ...
. For example, it is much easier to prove closure properties of regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s using NFAs than DFAs.
See also
* Deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
* Two-way nondeterministic finite automaton
In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.
Two-way deterministic finite automaton
A two-way deterministic finite automaton (2DFA) is an abstract ma ...
* Pushdown automaton
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is
a type of automaton that employs a stack.
Pushdown automata are used in theories about what can be computed by machines. They are more capa ...
* Nondeterministic Turing machine
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...
Notes
References
* 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. . ''(see section 1.2: Nondeterminism, pp. 47–63.)''
* John E. Hopcroft and Jeffrey D. Ullman, ''Introduction to Automata Theory, Languages, and Computation
''Introduction to Automata Theory, Languages, and Computation'' is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions begi ...
'', Addison-Wesley Publishing, Reading Massachusetts, 1979. . ''(See chapter 2.)''
{{DEFAULTSORT:Nondeterministic Finite-State Machine
Finite automata