Nondeterministic finite automaton: Difference between revisions

Revision as of 09:19, 13 December 2023

Revision as of 19:04, 22 December 2023

Line 58:

|-

| VALIGN=TOP | [[File:NFASimpleExample.svg|thumb|250px|The [[state diagram]] for ''M''. It is not deterministic since in state ''p'' reading a 1 can lead to ''p'' or to ''q''.]]

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

Line 92:

|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 doesn'tdoes 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>M</math>.

Line 108:

Conversely, for each NFA, there is a DFA such that it recognizes the same formal language. The DFA can be constructed using the [[powerset construction]].

This result shows that NFAs, despite their additional flexibility, are unable to recognize languages that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has ''n'' states, the resulting DFA may have up to 2^''n'' states, which sometimes makes the construction impractical for large NFAs.

==NFA with ε-moves==