Nondeterministic finite automaton
Type of finite-state machine in automata theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Non-deterministic finite automaton?
Summarize this article for a 10 year old
In automata theory, a finite-state machine is called a deterministic finite automaton (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, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language.[1] Like DFAs, NFAs only recognize regular languages.
NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott,[2] who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely, Kleene's algorithm 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 transducers, pushdown automata, alternating automata, ω-automata, and probabilistic automata. Besides the DFAs, other known special cases of NFAs are unambiguous finite automata (UFA) and self-verifying finite automata (SVFA).
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 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[3] and lead to an accepting state, the input is rejected.[4]: 19 [5]: 319
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.[4]: 19–20 [6]: 48 [7]: 56
For a more elementary introduction of the formal definition, see automata theory.
Automaton
An NFA is represented formally by a 5-tuple, , consisting of
- a finite set of states ,
- a finite set of input symbols ,
- a transition function : ,
- an initial (or start) state , and
- a set of states distinguished as accepting (or final) states .
Here, denotes the power set 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 recognized by and this language is denoted by .[5]: 320 [6]: 54
- Alternatively, is accepted if , where is defined recursively by:
- where is the empty string, and
- for all .
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.
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 (cf. upper left picture):
Input State |
0 | 1 |
---|---|---|
Since the set contains more than one state, is nondeterministic.
The language of can be described by the regular language given by the regular expression (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 does not 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.
A deterministic finite automaton (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 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.
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 2n states, which sometimes makes the construction impractical for large NFAs.