Content deleted Content added
m update 3rd ed refs |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (14 intermediate revisions by 7 users not shown) | |||
Line 9:
Like DFAs, NFAs only recognize [[regular language]]s.
NFAs were introduced in 1959 by [[Michael O. Rabin]] and [[Dana Scott]],
NFAs have been generalized in multiple ways, e.g., [[#NFA with ε-moves|nondeterministic finite automata with ε-moves]], [[finite-state transducer]]s, [[pushdown automaton|pushdown automata]], [[Alternating finite automaton|alternating automata]], [[ω-automaton|ω-automata]], and [[probabilistic automaton|probabilistic automata]].
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 28:
An ''NFA'' is represented formally by a 5-[[tuple]],
<math>(Q, \Sigma, \delta, q_0, F)</math>, consisting of
* a finite [[Set (mathematics)|set]] of [[State (computer science)|states]] <math>Q</math>,
* a finite set of input symbols called the [[
* a transition [[function (mathematics)|function]] <math>\delta</math> : <math>Q\times \Sigma \rightarrow \mathcal{P}(Q)</math>,
* an
* a set of
Here, <math>\mathcal{P}(Q)</math> denotes the [[power set]] of <math>Q</math>.
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>.
===Initial state===
Line 60:
| VALIGN=TOP | [[File:NFASimpleExample Runs10.gif|thumb|250px|All possible runs of ''M'' on input string "10"]]
|-
| COLSPAN=2 | [[File:NFASimpleExample Runs1011.gif|thumb|530px|All possible runs of ''M'' on input string "1011".<br />''Arc label:'' input symbol, ''node label'': state, ''{{color|#00c000|green}}:'' start state, ''{{color|#c00000|red}}:'' accepting state(s).
|-▼
! {{diagonal split header|State sequence|Input}}
|-▼
|-▼
|-▼
|}
]]
The following automaton <math>M</math>, with a binary alphabet, determines if the input ends with a 1.▼
|}▼
▲The following automaton
Let <math>M = (\{p, q\}, \{0, 1\}, \delta, p, \{q\})</math> where
the transition function <math>\delta</math> can be defined by this [[state transition table]] (cf. upper left picture):
:<math>\begin{array}{|c|cc|}
0 &
\\
▲|-
\hline
p &
\{p,q\}
▲|-
\\
q &
\emptyset
▲|}
\end{array}</math>
Since the set <math>\delta(p,1)</math> contains more than one state,
The language of
All possible state sequences for the input string "1011" are shown in the lower picture.
▲<!---replaced by image:---{| class="wikitable"
The string is accepted by
▲|-
▲!Input: || || 1 || || 0 || || 1 || || 1 ||
▲|-
▲|State sequence 1: || ''p'' || || ''q'' || ||'''?'''|| || || ||
▲|State sequence 2: || ''p'' || || ''p'' || || ''p'' || || ''q'' || || '''?'''
▲|State sequence 3: || ''p'' || || ''p'' || || ''p'' || || ''p'' || || ''q''
▲The string is accepted by <math>M</math> since one state sequence satisfies the above definition; it does not matter that other sequences fail to do so.
The picture can be interpreted in a couple of ways:
* In terms of the [[#Informal introduction|above]] "lucky-run" explanation, each path in the picture denotes a sequence of choices of
* In terms of the "cloning" explanation, each vertical column shows all clones of
The feasibility to read the same picture in two ways also indicates the equivalence of both above explanations.
* Considering the first of the [[#Recognized language|above]] formal definitions, "1011" is accepted since when reading it
* Concerning the second formal definition, bottom-up computation shows that <math>\delta^*(p,\epsilon) = \{ p \}</math>, hence <math>\delta^*(p,1) = \delta(p,1) = \{ p,q \}</math>, hence <math>\delta^*(p,10) = \delta(p,0) \cup \delta(q,0) = \{ p \} \cup \{\}</math>, hence <math>\delta^*(p,101) = \delta(p,1) = \{ p,q \}</math>, and hence <math>\delta^*(p,1011) = \delta(p,1) \cup \delta(q,1) = \{ p,q \} \cup \{\}</math>; since that set is not disjoint from <math>\{ q \}</math>, the string "1011" is accepted.
In contrast, the string "10" is rejected by
==Equivalence to DFA==
Line 147 ⟶ 151:
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 187 ⟶ 191:
|}
<math>M</math> can be viewed as the union of two [[deterministic finite automaton|DFA]]s: one with states <math>\{S_1, S_2\}</math> and the other with states <math>\{S_3, S_4\}</math>.
The language of <math>M</math> can be described by the [[regular language]] given by this [[regular expression]] <math>(1^{*}01^{*}
We define <math>M</math> using ε-moves but <math>M</math> can be defined without using ε-moves.
Line 211 ⟶ 215:
:*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 245 ⟶ 249:
* One can solve in linear time the [[emptiness problem]] for NFA, i.e., check whether the language of a given NFA is empty. To do this, we can simply perform a [[depth-first search]] from the initial state and check if some final state can be reached.
* It is [[PSPACE]]-complete to test, given an NFA, whether it is ''universal'', i.e., if there is a string that it does not accept.<ref>Historically shown in: {{Cite
* Given as input an NFA ''A'' and an integer n, the [[counting problem (complexity)|counting problem]] of determining how many words of length ''n'' are accepted by ''A'' is intractable; it is [[♯P|'''#P'''-hard]]. In fact, this problem is complete (under [[parsimonious reduction]]s) for the complexity class [[SpanL]].<ref>{{Cite journal |last1=Álvarez |first1=Carme |last2=Jenner |first2=Birgit |date=1993-01-04 |title=A very hard log-space counting class |url=https://dx.doi.org/10.1016/0304-3975%2893%2990252-O |journal=Theoretical Computer Science |volume=107 |issue=1 |pages=3–30 |doi=10.1016/0304-3975(93)90252-O |issn=0304-3975|url-access=subscription }}</ref>
==Application of NFA==
Line 261 ⟶ 265:
== References ==
*{{cite
*
* {{Hopcroft
* {{Hopcroft, Motwani, and Ullman 2006}} ''(See chapter 2, "Finite Automata".)''{{sfn whitelist|CITEREFHopcroftMotwaniUllman2006}}
{{Formal languages and grammars}}
Line 269 ⟶ 274:
{{DEFAULTSORT:Nondeterministic Finite-State Machine}}
[[Category:Finite-state
| |||