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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая версия)
 
Строка 1: Строка 1:
В отличие от [[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|конечных автоматов]], для [[МП-автоматы,_допуск_по_пустому_стеку_и_по_допускающему_состоянию,_эквивалентность|МП-автоматов]] недетерминизм является существенным. [[Детерминированные_автоматы_с_магазинной_памятью|ДМП-автоматы]] распознают строгое подмножество языков, распознаваемых МП-автоматами или КС-грамматиками.
+
В отличие от [[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|конечных автоматов]], для [[МП-автоматы,_допуск_по_пустому_стеку_и_по_допускающему_состоянию,_эквивалентность|МП-автоматов]] недетерминизм является существенным. [[Детерминированные_автоматы_с_магазинной_памятью|ДМП-автоматы]] распознают не все языки, распознаваемые МП-автоматами или КС-грамматиками.
  
 
{{Теорема
 
{{Теорема

Версия 23:48, 7 декабря 2011

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

Теорема:
Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают.
Доказательство:
[math]\triangleright[/math]
Автомат [math]M[/math]

Рассмотрим язык [math]L=\left\{0^n1^n \cup 0^n1^{2n}\right\}[/math]. Очевидно, что язык [math]L[/math] является контекстно-свободным. Пусть существует ДМП-автомат с допуском по допускающему состоянию [math]M[/math], распознающий его. В силу детерминированности автомата [math](s, z_0, 0^n1^{2n})\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' \cup L[/math], который, в свою очередь, тоже не контекстно-свободен. Для начала построим по автомату [math]M[/math] автомат [math]M'[/math], заменив все вхождения символа [math]1[/math] на символ [math]2[/math]. Далее объединим автоматы [math]M[/math] и [math]M'[/math] в автомат [math]M''[/math], соединив допускающие состояния [math]\varepsilon[/math]-переходами (как показано на картинке). Автомат [math]M''[/math] является недетерминированным МП-автоматом, и принимает не контекстно-свободный язык [math]L' \cup L[/math].

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