Editing Nondeterministic finite automaton (section)

==Informal introduction==

There are at least two equivalent ways to describe the behavior of an NFA. The first way makes use of the [[Nondeterministic algorithm|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<ref>A choice sequence may lead into a "dead end" where no transition is applicable for the current input symbol; in this case it is considered unsuccessful.</ref> and lead to an accepting state, the input is rejected.{{sfn|Hopcroft|Ullman|1979|pp=19-20}}<ref name="Aho.Hopcroft.Ullman.1974">{{cite book | isbn=0-201-00029-6 | author=Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman | title=The Design and Analysis of Computer Algorithms | url=https://archive.org/details/designanalysisof00ahoarich | url-access=registration | location=Reading/MA | publisher=Addison-Wesley | year=1974 }}</ref>{{rp|319}}{{sfn|Hopcroft|Motwani|Ullman|2006|pp=55-6}}

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.{{sfn|Hopcroft|Ullman|1979|pp=19–20}}<!---not an error: Hopcroft and Ullman use both informal explanations--->{{sfn|Sipser|1997|p=48}}{{sfn|Hopcroft|Motwani|Ullman|2006|pp=55-6}}