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