Nondeterministic finite automaton: Difference between revisions

Revision as of 01:41, 29 November 2024

Latest revision as of 08:59, 25 August 2025

(9 intermediate revisions by 7 users not shown)

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 [[inputAlphabet (computer symbolscience)|alphabet]]s <math>\Sigma</math>,

* a transition [[function (mathematics)|function]] <math>\delta</math> : <math>Q\times \Sigma \rightarrow \mathcal{P}(Q)</math>,

* an ''initial'' (or ''start'') state <math>q_0 \in Q</math>, and

* a set of states <math>F</math> distinguished as ''accepting'' (or ''final'') ''states'' <math>F \subseteq Q</math>.

Here, <math>\mathcal{P}(Q)</math> denotes the [[power set]] of <math>Q</math>.

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).]]

<!---replaced by image:---{| class="wikitable"

|-

! {{diagonal split header|State sequence|Input}}

!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 following automaton <math>M</math>, with a binary alphabet, determines if the input ends with a 1.

|}

The following automaton <math>{{mvar|M</math>}}, with a binary alphabet, determines if the input ends with a 1.

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|}

:{| class="wikitable" style="text-align:center;"

! \bcancel{{diagonal split header|}_\text{State|}\quad {}^\text{Input}} &

0 &

! 0

! 1

\\

|-

\hline

! <math>p</math>

p &

| <math>\{p\}</math>

| <math>\{p,q\}</math> &

\{p,q\}

|-

\\

! <math>q</math>

q &

| <math>\emptyset</math>

| <math>\emptyset</math> &

\emptyset

|}

\end{array}</math>

Since the set <math>\delta(p,1)</math> contains more than one state, <math>{{mvar|M</math>}} is nondeterministic.

The language of <math>{{mvar|M</math>}} can be described by the [[regular language]] given by the [[regular expression]] <code>(0|1)*1</code>.

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 <math>{{mvar|M</math>}} since one state sequence satisfies the above definition; it does not matter that other sequences fail to do so.

|-

!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 <math>{{mvar|M</math>}}.

* In terms of the "cloning" explanation, each vertical column shows all clones of <math>{{mvar|M</math>}} at a given point in time, multiple arrows emanating from a node indicate cloning, a node without emanating arrows indicating the "death" of a clone.

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 <math>{{mvar|M</math>}} may traverse the state sequence <math>\langle r_0,r_1,r_2,r_3,r_4 \rangle = \langle p, p, p, p, q \rangle</math>, which satisfies conditions 1 to 3.

* 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 <math>{{mvar|M</math>}} (all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state, <math>{{mvar|q</math>}}, by reading the final 0 symbol. While <math>{{mvar|q</math>}} can be reached after consuming the initial "1", this does not mean that the input "10" is accepted; rather, it means that an input string "1" would be accepted.

==Equivalence to DFA==

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^{*}001^{*})^{*} \cup (0^{*}10^{*}110^{*})^{*}</math>.

We define <math>M</math> using ε-moves but <math>M</math> can be defined without using ε-moves.

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 journalbook |last1=Meyer |first1=A. R. |last2=Stockmeyer |first2=L. J. |datetitle=13th Annual Symposium on Switching and Automata Theory (Swat 1972-10-25) |titlechapter=The equivalence problem for regular expressions with squaring requires exponential space |journaldate=Proceedings of the 13th Annual Symposium on Switching and Automata Theory (SWAT)1972-10-25 |___location=USA |publisher=IEEE Computer Society |pages=125–129 |doi=10.1109/SWAT.1972.29}} For a modern presentation, see [http://www.lsv.fr/~jacomme/1718/ca/td4_sol.pdf]</ref> As a consequence, the same is true of the ''inclusion problem'', i.e., given two NFAs, is the language of one a subset of the language of the other.

* 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 262 ⟶ 266:

== References ==

*{{cite journal |doi=10.1147/rd.32.0114 |last1=Rabin |first1=M. O. |last2=Scott |first2=D. |title=Finite Automata and Their Decision Problems |journal=IBM Journal of Research and Development |volume=3 |issue=2 |pages=114–125 |date=April 1959 }}

* {{Sipser 1997}} ''(See §1.2: Nondeterminism, pp. 47–63.)''{{sfn whitelist|CITEREFSipser1997}}

* {{Hopcroft and Ullman 1979|author-link=no|title-link=no}}{{sfn whitelist|CITEREFHopcroftUllman1979}}

* {{Hopcroft, Motwani, and Ullman 2006}} ''(See chapter 2, "Finite Automata".)''{{sfn whitelist|CITEREFHopcroftMotwaniUllman2006}}

{{Formal languages and grammars}}

Line 270 ⟶ 274:

{{DEFAULTSORT:Nondeterministic Finite-State Machine}}

[[Category:Finite-state automatamachines]]