МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
Допустимость по заключительному состоянию
- Определение: Пусть - МП-автомат. Тогда языком, допускаемым автоматом по заключительному состоянию, является для некоторого состояния и произвольной магазинной цепочки . Начиная с стартовой вершины и с на входе, автомат прочитывает слово и достигает допускающего состояния. Содержимое магазина в этот момент не имеет значения.
Допустимость по пустому магазину
- Определение: Для МП-автомата определим множество допускающих слов как , где - произвольное состояние. Таким образом автомат прочитывает слово , полностью опустошив свой магазин. Множество заключительных состояний не имеет значение.
Эквивалентность автоматов
- Теорема: Классы языков, допускаемых МП-автоматами по заключительному состоянию и по пустому магазину (стеку), совпадают.
- Доказательство: Исходя из МП-автомата , допускающего язык по заключительному состоянию, построим другой МП-автомат , который допускает язык по пустому стеку.
1. Добавим переходы по
из каждого допускающего состояния автомата в новое состояние , которое отвечает за очистку стека. Находясь в состоянии , автомат опустошает свой магазин и ничего не прочитывает на входе. Таким образом, как только исходный автомат приходит в допускающее состояние, прочитав слово , опустошает свой магазин, также прочитав слово .2. Во избежание случая, когда
может опустошить свой магазин без допуска, использует свой маркер дна . Добавление нового стартового состояния позволяет затолкнуть маркер автомата в магазин и перейти в стартовое состояние .3. Каждый переход
есть и у автомата , символ хранится в магазине под всеми символами из и является символом, по которому нет переходов в . Тогда может совершить следующие действия: , что означает допускает слово по пустому магазину.
- Доказательство: Исходя из МП-автомата , допускающего язык по пустому стеку, построим МП-автомат , допускающий по заключительному состоянию.