Content deleted Content added
m →Two-way pushdown automaton: Putting refs on second line causes formatting problems |
m \mathrm |
||
Line 30:
* <math>L</math> is the left endmarker
* <math>R</math> is the right endmarker
* <math>\delta: Q \times (\Sigma \cup \{L,R\}) \rightarrow Q \times \{\mathrm{left,right}\}</math>
* <math>s</math> is the start state
* <math>t</math> is the end state
Line 37:
In addition, the following two conditions must also be satisfied:
* For all <math>q \in Q</math>
:<math>\delta(q,L)=(q^\prime,\mathrm{right})</math> for some <math>q^\prime \in Q</math>
:<math>\delta(q,R)=(q^\prime,\mathrm{left})</math> for some <math>q^\prime \in Q</math>
It says that there must be some transition possible when pointer on the alphabet reaches the end.
* For all symbols <math>\sigma \in \Sigma \cup \{L\}</math>
Line 50:
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 \{\mathrm{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.
| |||