NFA is formally represented by the 5-tuple, where: In general, NFA can have ε transitions and missing transitions for any given input symbol. Equivalently, it rejects, if, no matter what transitions are applied, it would not end in an accepting state. 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. The notion of accepting an input is similar to that for the DFA. They are usually labeled with the Greek letter λ or ε. Transformations to new states without consuming an input symbol are called lambda transitions or epsilon transitions. Thus, before consuming letter a, the NFA-epsilon may be in any one of the states out of the set. Both types of automata recognize only regular languages.Īn extension of the NFA is the NFA-lambda (also known as NFA-epsilon or the NFA with epsilon moves), which allows a transformation to a new state without consuming any input symbols.įor example, if it is in state 1, with the next input symbol an a, it can move to state 2 without consuming any input symbols, and thus there is an ambiguity: is the system in state 1, or state 2, before consuming the letter a? Because of this ambiguity, it is more convenient to talk of the set of possible states the system may be in. Although the DFA and NFA have distinct definitions, it may be shown in the formal theory that they are equivalent, in that, for any given NFA, one may construct an equivalent DFA, and vice-versa: this is the powerset construction. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined. Nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |