Content deleted Content added
→References: update ref |
→Informal introduction: update ref to 3rd ed (using {sfn}) |
||
Line 18:
==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.<ref name="Hopcroft.Ullman.1979">{{cite book | isbn=0-201-02988-X | author=John E. Hopcroft and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | ___location=Reading/MA | publisher=Addison-Wesley | year=1979 | url=https://archive.org/details/introductiontoau00hopc }}</ref>{{rp|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.<ref name="Hopcroft.Ullman.1979"/>{{rp|19–20}}<!---not an error: Hopcroft and Ullman use both informal explanations---><ref name="Sipser.1997">{{cite book | author=Michael Sipser | title=Introduction to the Theory of Computation | ___location=Boston/MA | publisher=PWS Publishing Co. | year=1997 | isbn=0-534-94728-X | url=https://archive.org/details/introductiontoth00sips }}</ref>{{rp|48}}
==Formal definition==
| |||