Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами — различия между версиями
Строка 16: | Строка 16: | ||
Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык <tex>L</tex>. Но из того, что <tex>L</tex> — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его. | Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык <tex>L</tex>. Но из того, что <tex>L</tex> — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его. | ||
}} | }} | ||
+ | |||
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Контекстно-свободные грамматики]] |
Версия 12:50, 2 марта 2012
В отличие от конечных автоматов, для МП-автоматов недетерминизм является существенным. ДМП-автоматы распознают не все языки, распознаваемые МП-автоматами или КС-грамматиками.
Лемма: |
Язык не является контекстно-свободным. |
Доказательство: |
Для фиксированного | рассмотрим слово . Пусть разбили на произвольным образом. Так как , то в слове не содержится либо ни одного символа , либо ни одного символа . Для любого такого разбиения выбираем и получаем, что количество символов изменилось, а количество либо , либо осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык не является контекстно-свободным по лемме о разрастании для КС-грамматик.
Теорема: |
Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают. |
Доказательство: |
Рассмотрим язык . Очевидно, что язык является контекстно-свободным. Пусть существует ДМП-автомат с допуском по допускающему состоянию , распознающий его. В силу детерминированности автомата , причём . Рассмотрим также язык .Построим на основе Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык недетерминированный МП-автомат, распознающий язык . Для начала построим по автомату автомат , заменив все вхождения символа на символ . Далее объединим автоматы и в автомат , соединив допускающие состояния -переходами (как показано на картинке). Автомат является недетерминированным МП-автоматом, и принимает не контекстно-свободный язык . . Но из того, что — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его. |