Content deleted Content added
m →References: fix sipser ref |
→References: mv 1st ed, add {sfn}s |
||
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.
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.
==Formal definition==
Line 49:
*# <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>.
===Initial state===
Line 147:
The automaton is said to accept a string <math>w</math> if
:<math>\delta^*(q_0,w) \cap F \neq \emptyset ,</math>
that is, if reading <math>w</math> may drive the automaton from its start state <math>q_0</math> to some accepting state in <math>F .</math>
===Example===
Line 211:
:*If <math>\delta'^*(q_0,w)</math> contains a state in <math>F' \setminus \{ q_0 \} ,</math> then <math>\delta^*(q_0,w)</math> contains the same state, which lies in <math>F</math>.
:*If <math>\delta'^*(q_0,w)</math> contains <math>q_0 ,</math> and <math>q_0 \in F ,</math> then <math>\delta^*(q_0,w)</math> also contains a state in <math>F ,</math> viz. <math>q_0 .</math>
:*If <math>\delta'^*(q_0,w)</math> contains <math>q_0 ,</math> and <math>q_0 \not\in F ,</math> but <math>q_0\in F',</math> then there exists a state in <math>E(q_0)\cap F</math>, and the same state must be in <math display=inline>\delta^*(q_0,w) = \bigcup_{r \in \delta^*(q,v)} E(\delta(r,a)) .</math>
Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.
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 | first=Michael |last=Sipser | title=Introduction to the Theory of Computation
* {{cite book | isbn=0-201-02988-X | first1=John E. |last1=Hopcroft |first2=Jeffrey D. |last2= Ullman | title=Introduction to Automata Theory, Languages, and Computation | publisher=Addison-Wesley | year=1979 | url=https://archive.org/details/introductiontoau00hopc |edition=1st }}
* {{Hopcroft, Motwani, and Ullman 2006}} ''(See chapter 2, "Finite Automata".)''
| |||