Content deleted Content added
m update 3rd ed refs |
use {cite book} for Sipser 1997 |
||
Line 20:
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---
==Formal definition==
Line 44:
*# <math>r_{i+1} \in \delta (r_i, a_{i+1})</math>, for <math>i = 0, \ldots, n-1</math>
*# <math>r_n \in F</math>.
:In words, the first condition says that the machine starts in the start state <math>q_0</math>. The second condition says that given each character of string <math>w</math>, the machine will transition from state to state according to the transition function <math>\delta</math>. The last condition says that the machine accepts <math>w</math> if the last input of <math>w</math> causes the machine to halt in one of the accepting states. In order for <math>w</math> to be accepted by <math>M</math>, 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 <math>q_0</math> to a state from <math>F</math> by following <math>w</math>, it is said that the automaton ''rejects'' the string. The set of strings <math>M</math> accepts is the [[Formal language|language]] ''recognized'' by <math>M</math> and this language is denoted by <math>L(M)</math>.<ref name="Aho.Hopcroft.Ullman.1974"/>{{rp|320}}<!---using "deduction" relation "\vdash"---
*Alternatively, <math>w</math> is accepted if <math>\delta^*(q_0, w) \cap F \not = \emptyset</math>, where <math>\delta^*: Q \times \Sigma^* \rightarrow \mathcal{P}(Q)</math> is defined [[recursion (computer science)|recursively]] by:
*# <math>\delta^*(r, \epsilon) = \{r\}</math> where <math>\epsilon</math> is the empty string, and
*# <math>\delta^*(r, xa)= \bigcup_{r' \in \delta^*(r, x)} \delta(r', a)</math> for all <math>x \in \Sigma^*, a \in \Sigma</math>.
:In words, <math>\delta^*(r, x)</math> is the set of all states reachable from state <math>r</math> by consuming the string <math>x</math>. The string <math>w</math> is accepted if some accepting state in <math>F</math> can be reached from the start state <math>q_0</math> by consuming <math>w</math>.<ref name="Hopcroft.Ullman.1979"/>{{rp|21}}{{sfn|Hopcroft|Motwani|Ullman|2006|
===Initial state===
Line 262:
== References ==
* M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", ''IBM Journal of Research and Development'', '''3''':2 (1959) pp. 115–125.
* {{cite book | author=Michael Sipser
* {{Hopcroft, Motwani, and Ullman 2006}} ''(See chapter 2, "Finite Automata".)''
| |||