Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
[[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|В отличие от конечных автоматов]], для [[МП-автоматы,_допуск_по_пустому_стеку_и_по_допускающему_состоянию,_эквивалентность|МП-автоматов]] недетерминизм является существенным. [[Детерминированные_автоматы_с_магазинной_памятью|ДМП-автоматы]] распознают не все языки, распознаваемые МП-автоматами или [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматиками]]. | [[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|В отличие от конечных автоматов]], для [[МП-автоматы,_допуск_по_пустому_стеку_и_по_допускающему_состоянию,_эквивалентность|МП-автоматов]] недетерминизм является существенным. [[Детерминированные_автоматы_с_магазинной_памятью|ДМП-автоматы]] распознают не все языки, распознаваемые МП-автоматами или [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматиками]]. | ||
Текущая версия на 19:33, 4 сентября 2022
В отличие от конечных автоматов, для МП-автоматов недетерминизм является существенным. ДМП-автоматы распознают не все языки, распознаваемые МП-автоматами или КС-грамматиками.
Лемма: |
Язык не является контекстно-свободным. |
Доказательство: |
Для доказательства леммы воспользуемся леммой о накачке для КС-грамматик. Для фиксированного рассмотрим слово . Пусть разбили на произвольным образом. Так как , то в слове не содержится либо ни одного символа , либо ни одного символа . Для любого такого разбиения выбираем и получаем, что количество символов изменилось, а количество либо , либо осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык не является контекстно-свободным по лемме о разрастании для КС-грамматик. |
Теорема: |
Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают. |
Доказательство: |
Рассмотрим язык . Очевидно, что язык является контекстно-свободным.
|
См. также
- Автоматы с магазинной памятью
- Допуск по пустому стеку и по допускающему состоянию
- Детерминированные автоматы с магазинной памятью
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
- Википедия — Автомат с магазинной памятью