Двусторонний детерминированный конечный автомат

Определение:

Двусторонний детерминированный конечный автомат (2ДКА) (англ. Two-way deterministic finite automaton (2DFA)) — набор из восьми элементов [math]\langle \Sigma , Q, L, R, s, t, r, \delta \rangle[/math], где [math]\Sigma[/math] — алфавит (англ. alphabet), [math]Q[/math] — множество состояний (англ. finite set of states), [math]L \notin \Sigma[/math] — левый маркер конца строки, [math]R \notin \Sigma[/math] — правый маркер конца строки, [math]s \in Q[/math] — начальное (стартовое) состояние (англ. start state), [math]t \in Q[/math] — допускающее состояние (англ. accept state), [math]r \in Q[/math] — отвергающее состояние (англ. reject state), [math]\delta : Q \times \{\Sigma \cup \{L, R\}\} \to Q \times \{left, right\}[/math] — функция переходов (англ. transition function).

Также должны быть удовлетворены следующие условия:

[math]\forall q \in Q[/math]

• [math]\delta(q, L) = (u, right)[/math] для некоторого [math]u \in Q[/math],
• [math]\delta(q, R) = (v, left)[/math] для некоторого [math]v \in Q[/math],

и [math]\forall b \in \Sigma \cup \{L\}[/math]

• [math]\delta(t, b) = (t, right)[/math],
• [math]\delta(r, b) = (r, right)[/math],
• [math]\delta(t, R) = (t, left)[/math],
• [math]\delta(r, R) = (r, left)[/math].

См. также

• Детерминированные конечные автоматы