Content deleted Content added
m →State complexity tradeoffs: Corrected the 2FA to NFA tradeoff |
|||
Line 49:
== Two-way nondeterministic finite automaton ==
A two-way nondeterministic finite automaton (2NFA) may have multiple transitions defined in the same configuration. Its transition function is
* <math>\delta: Q \times (\Sigma \cup \{L,R\}) \rightarrow 2^{Q \times \{left,right\}}</math>. Like a standard one-way [[Nondeterministic finite automaton|NFA]], a 2NFA accepts a string if at least one of the possible computations is accepting. Like the 2DFAs, the 2NFAs also accept only regular languages. ==State complexity tradeoffs==
| |||