Nondeterministic finite automaton: Difference between revisions

Revision as of 14:02, 29 January 2025

Revision as of 11:28, 14 February 2025

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"

|-

!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==