Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
Версия от 23:48, 7 декабря 2011; Nikita.Ofitserov (обсуждение | вклад)
В отличие от конечных автоматов, для МП-автоматов недетерминизм является существенным. ДМП-автоматы распознают не все языки, распознаваемые МП-автоматами или КС-грамматиками.
Теорема: |
Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают. |
Доказательство: |
Рассмотрим язык Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык . Очевидно, что язык является контекстно-свободным. Пусть существует ДМП-автомат с допуском по допускающему состоянию , распознающий его. В силу детерминированности автомата , причём . Рассмотрим также язык , который, как известно, контекстно-свободным не является. Построим на основе недетерминированный МП-автомат, распознающий , который, в свою очередь, тоже не контекстно-свободен. Для начала построим по автомату автомат , заменив все вхождения символа на символ . Далее объединим автоматы и в автомат , соединив допускающие состояния -переходами (как показано на картинке). Автомат является недетерминированным МП-автоматом, и принимает не контекстно-свободный язык . . Но из того, что — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его. |