Nondeterministic finite automaton with ε-moves

In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if 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.Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, 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 automaton with ε-moves, finite state transducers, pushdown automata, alternating automata, ω-automata, and probabilistic automata.Besides the DFAs, other known special cases of NFAsare unambiguous finite automata (UFA)and self-verifying finite automata (SVFA). An NFA, similar to a DFA, consumes a string of input symbols. For each input symbol, it transitions to a new state until all input symbols have been consumed.Unlike a DFA, it is non-deterministic, i.e., for some state and input symbol, the next state may be nothing or one or two or more possible states. Thus, in the formal definition, the next state is an element of the power set of the states, which is a set of states to be considered at once.The notion of accepting an input is similar to that for the DFA.When the last input symbol is consumed, the NFA accepts if and only if there is some set of transitions that will take it to an accepting state. Equivalently, it rejects, if, no matter what transitions are applied, it would not end in an accepting state. An NFA is represented formally by a 5-tuple, ( Q , Σ , Δ , q 0 , F ) {displaystyle (Q,Sigma ,Delta ,q_{0},F)} , consisting of Here, P ( Q ) {displaystyle P(Q)} denotes the power set of Q {displaystyle Q} .Let w = a 1 a 2 . . . a n {displaystyle w=a_{1}a_{2}...a_{n}} be a word over the alphabet Σ {displaystyle Sigma } . The automaton M {displaystyle M} accepts the word w {displaystyle w} if a sequence of states, r 0 , r 1 , . . . , r n {displaystyle r_{0},r_{1},...,r_{n}} , exists in Q {displaystyle Q} with the following conditions: In words, the first condition says that the machine starts in the start state q 0 {displaystyle q_{0}} . The second condition says that given each character of string w {displaystyle w} , the machine will transition from state to state according to the transition function Δ {displaystyle Delta } . The last condition says that the machine accepts w {displaystyle w} if the last input of w {displaystyle w} causes the machine to halt in one of the accepting states. In order for w {displaystyle w} to be accepted by M {displaystyle M} , 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 q 0 {displaystyle q_{0}} to a state from F {displaystyle F} by following w {displaystyle w} , it is said that the automaton rejects the string. The set of strings M {displaystyle M} accepts is the language recognized by M {displaystyle M} and this language is denoted by L ( M ) {displaystyle L(M)} .