Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами

Материал из Викиконспекты
Версия от 20:50, 14 января 2016; AReunov (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

В отличие от конечных автоматов, для МП-автоматов недетерминизм является существенным. ДМП-автоматы распознают не все языки, распознаваемые МП-автоматами или КС-грамматиками.

Лемма:
Язык [math]L' = \left\{0^{n}1^{n}2^{n}\right\} \cup \left\{0^n1^n\right\} \cup \left\{0^n1^{2n}\right\}[/math] не является контекстно-свободным.
Доказательство:
[math]\triangleright[/math]
Для доказательства леммы воспользуемся леммой о накачке для КС-грамматик. Для фиксированного [math]n[/math] рассмотрим слово [math]\omega=0^n 1^n 2^n[/math]. Пусть [math]\omega[/math] разбили на [math]u, v, x, y, z[/math] произвольным образом. Так как [math]|vxy|\leqslant n[/math], то в слове не содержится либо ни одного символа [math]0[/math], либо ни одного символа [math]2[/math]. Для любого такого разбиения выбираем [math]k=2[/math] и получаем, что количество символов [math]1[/math] изменилось, а количество либо [math]0[/math], либо [math]2[/math] осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык [math]L'[/math] не является контекстно-свободным по лемме о разрастании для КС-грамматик.
[math]\triangleleft[/math]
Теорема:
Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают.
Доказательство:
[math]\triangleright[/math]
Автомат [math]M[/math]
Автомат [math]M''[/math]

Рассмотрим язык [math]L=\left\{0^n1^n\right\} \cup \left\{0^n1^{2n}\right\}[/math]. Очевидно, что язык [math]L[/math] является контекстно-свободным.


Так как множества языков, распознаваемых ДМП-автомат с допуском по допускающему состоянию и ДМП-автомат с допуском по пустому стеку совпадают (см. соответствующую теорему), будем рассматривать в доказательстве ДМП-автомат с допуском по допускающему состоянию.


Пусть существует ДМП-автомат с допуском по допускающему состоянию [math]M[/math], распознающий язык [math]L[/math]. В силу детерминированности автомата [math](s, z_0, 0^n1^{n})\vdash^*(q_1, \gamma_1, 1^n)\vdash^*(q_2, \gamma_2, \varepsilon)[/math], причём [math]q_1, q_2 \in T[/math].
Рассмотрим также язык [math]L''=\left\{0^n1^n2^n\right\}[/math].


Построим на основе [math]M[/math] недетерминированный МП-автомат, распознающий язык

[math]L' = \left\{0^{n}1^{n}2^{n}\right\} \cup \left\{0^n1^n\right\} \cup \left\{0^n1^{2n}\right\}[/math].
  1. Для начала построим по автомату [math]M[/math] автомат [math]M'[/math], заменив все вхождения символа [math]1[/math] на символ [math]2[/math].
  2. Далее объединим автоматы [math]M[/math] и [math]M'[/math] в автомат [math]M''[/math], соединив допускающие состояния [math]\varepsilon[/math]-переходами (как показано на картинке).


Автомат [math]M''[/math] является недетерминированным МП-автоматом, и принимает не контекстно-свободный язык [math]L'[/math].

Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык [math]L[/math]. Но из того, что [math]L[/math] — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его.
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]