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

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

Двусторонний детерминированный конечный автомат (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].

Описание

Зафиксируем [math]x \in \Sigma^*[/math], где [math]x = a_1 a_2 a_3 \dots a_n[/math]. Пусть [math]a_0 = L[/math] и [math]a_{n+1}=R[/math]. Тогда [math]a_0 a_1 a_2 \dots a_n a_{n+1} = L x R[/math].

Пример

Рассмотрим следующий язык [math]L_n = (a+b)^∗a(a+b)^{n-1}a(a+b)^∗[/math] при [math]\forall n \gt 0[/math].

Он может быть легко распознан с помощью следующего недетерменированного конечного автомата.

Теперь построим на его основе ДКА. Мы можем построить автомат [math]A_n[/math], который запоминает последние [math]n[/math] входных символов. Следовательно, когда мы находимся с состоянии, соответствующему подстроке [math]\sigma_1 \sigma_2 \dots \sigma_n[/math], и читаем очередной символ [math]\gamma[/math], то мы переходим в состояние, которому уже будет соответствовать подстрока [math]\sigma_2 \sigma_3 \dots \sigma_n \gamma[/math]. Однако, в случае [math]\sigma_1 = \gamma = a[/math] автомат переходит в допускающее состояние, где в цикле может переходить на любому символу. Следует отметить, что такая стратегия строит ДКА c [math]2^n + 1[/math] состояниями. Ниже представлен автомат [math]A_3[/math], который распознает язык [math]L_3[/math].

Покажем, что построенные таким образом автоматы будут минимальными.

• Каждые две попарно различных строки [math]x[/math] и [math]y[/math] длины [math]n[/math] различимы. Чтобы доказать это, достаточно рассмотреть строку [math]b^{i-1}a[/math], где [math]i : 1 \leqslant i \leqslant n[/math] — самая левая позиция символа, в которой начинают различаться строки [math]x[/math] и [math]y[/math], и проверить, что ровно одна строка [math]xb^{i-1}a[/math] или [math]yb^{i-1}a[/math] принадлежит [math]L_n[/math].
• Каждая строка длины [math]n[/math] не принадлежит [math]L_n[/math] и, следовательно, различима от строки [math]a^{n+1}[/math], которая принадлежит [math]L_n[/math].
• Таким образом, [math]2^n + 1[/math] строк в [math]\Sigma^n \cup \{a^{n+1}\}[/math] являются попарно различимыми для [math]L_n[/math]. Как следствие, [math]2^n + 1[/math] — минимальное количество состояний для ДКА, который способен распознать язык [math]L_n[/math].

См. также

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