Двусторонний детерминированный конечный автомат — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
Строка 22: Строка 22:
  
 
Теперь построим на его основе ДКА. Мы можем построить автомат <tex>A_n</tex>, который запоминает последние <tex>n</tex> входных символов. Следовательно, когда мы находимся с состоянии, соответствующему подстроке <tex>\sigma_1 \sigma_2 \dots \sigma_n</tex>, и читаем очередной символ <tex>\gamma</tex>, то мы переходим в состояние, которому уже будет соответствовать подстрока <tex>\sigma_2 \sigma_3 \dots \sigma_n \gamma</tex>. Однако, в случае <tex>\sigma_1 = \gamma = a</tex> автомат переходит в допускающее состояние, где в цикле может переходить на любому символу. Следует отметить, что такая стратегия строит ДКА c <tex>2^n + 1</tex> состояниями. Ниже представлен автомат <tex>A_3</tex>, который распознает язык <tex>L_3</tex>.
 
Теперь построим на его основе ДКА. Мы можем построить автомат <tex>A_n</tex>, который запоминает последние <tex>n</tex> входных символов. Следовательно, когда мы находимся с состоянии, соответствующему подстроке <tex>\sigma_1 \sigma_2 \dots \sigma_n</tex>, и читаем очередной символ <tex>\gamma</tex>, то мы переходим в состояние, которому уже будет соответствовать подстрока <tex>\sigma_2 \sigma_3 \dots \sigma_n \gamma</tex>. Однако, в случае <tex>\sigma_1 = \gamma = a</tex> автомат переходит в допускающее состояние, где в цикле может переходить на любому символу. Следует отметить, что такая стратегия строит ДКА c <tex>2^n + 1</tex> состояниями. Ниже представлен автомат <tex>A_3</tex>, который распознает язык <tex>L_3</tex>.
 +
 +
Покажем, что построенные таким образом автоматы будут минимальными.
 +
* Каждые две попарно различных строки <tex>x</tex> и <tex>y</tex> длины <tex>n</tex> различимы. Чтобы доказать это, достаточно рассмотреть строку <tex>b^{i-1}a</tex>, где <tex>i : 1 \leqslant i \leqslant n</tex> {{---}} самая левая позиция символа, в которой начинают различаться строки <tex>x</tex> и <tex>y</tex>, и проверить, что ровно одна строка <tex>xb^{i-1}a</tex> или <tex>yb^{i-1}a</tex> принадлежит <tex>L_n</tex>.
 +
* Каждая строка длины <tex>n</tex> не принадлежит <tex>L_n</tex> и, следовательно, различима от строки <tex>a^{n+1}</tex>, которая принадлежит <tex>L_n</tex>.
 +
* Таким образом, <tex>2^n + 1</tex> строк в <tex>\Sigma^n \cup \{a^{n+1}\}</tex> являются попарно различимыми для <tex>L_n</tex>. Как следствие, <tex>2^n + 1</tex> {{---}} минимальное количество состояний для ДКА, который способен распознать язык <tex>L_n</tex>.
  
 
== См. также ==
 
== См. также ==

Версия 20:00, 9 января 2015

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

См. также

Источники информации