418
правок
Изменения
Нет описания правки
* <tex>\delta(t, R) = (t, left)</tex>,
* <tex>\delta(r, R) = (r, left)</tex>.
== Описание ==
Зафиксируем <tex>x \in \Sigma^*</tex>, где <tex>x = a_1 a_2 a_3 \dots a_n</tex>. Пусть <tex>a_0 = L</tex> и <tex>a_{n+1}=R</tex>. Тогда <tex>a_0 a_1 a_2 \dots a_n a_{n+1} = L x R</tex>.
== Пример ==
Рассмотрим следующий язык <tex>L_n = (a+b)^∗a(a+b)^{n-1}a(a+b)^∗</tex> при <tex>\forall n > 0</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>.
== См. также ==
