Content deleted Content added
No edit summary Tags: Reverted Mobile edit Mobile web edit |
Undid revision 1169284844 by 2601:646:9A00:C0F0:95F2:4953:D129:A1F5: "former" could be misunderstood as "immediately preceding" |
||
Line 4:
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state transition.
A '''nondeterministic finite automaton''' ('''NFA'''), or '''nondeterministic finite-state machine''', does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term '''NFA''' is used in a narrower sense, referring to an NFA that is ''not'' a DFA, but
Using the [[subset construction algorithm]], each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same [[formal language]].<ref>{{cite book |title=Introduction to Languages and the Theory of Computation |last1=Martin |first1=John |year=2010 |page=108 |publisher=McGraw Hill |isbn= 978-0071289429}}</ref>
| |||