Математическая теория формальных языков



         

Определение автомата с магазинной памятью


Определение 10.1.1.

Автомат с магазинной памятью (МП-автомат, магазинный автомат, стековый автомат, pushdown automaton) - это шестерка , где , , и

- конечные множества, ,

и

Здесь Q - множество состояний, - входной алфавит, - алфавит магазинной памяти (stack alphabet), - множество переходов (transition relation), элементы I называются начальными состояниями, элементы F - заключительными или допускающими состояниями.

Пример 10.1.2.

Пусть Q = {1,2}, , ,

, . Тогда - МП-автомат.

Замечание 10.1.3.

МП-автоматы можно изображать в виде диаграмм состояний. На диаграмме каждое состояние обозначается кружком, а переход - стрелкой. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое допускающее состояние отмечается на диаграмме двойным кружком. Стрелка с пометкой , ведущая из p в q, показывает, что

является переходом данного МП-автомата.

Пример 10.1.4.

Ниже приведена диаграмма МП-автомата из примера 10.1.2.

Определение 10.1.5.

Конфигурацией МП-автомата называется любая тройка , где , , .

Определение 10.1.6.

Определим на множестве всех конфигураций МП-автомата

бинарное отношение

(такт работы) следующим образом. Если ,

и , то .

Замечание 10.1.7

Обычно из контекста ясно, о каком МП-автомате идет речь. Тогда вместо

будем писать .

Пример 10.1.8.

Для МП-автомата из примера 10.1.2 выполняется

и .

Определение 10.1.9.

Бинарное отношение

определяется как рефлексивное, транзитивное замыкание отношения .

Пример 10.1.10.

Для МП-автомата из примера 10.1.2 выполняется

и .

Лемма 10.1.11.

Если

и , то .

Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации

в конфигурацию .

Определение 10.1.12.

Слово

допускается МП-автоматом , если найдутся такие состояния

и , что .

Определение 10.1.13.

Язык, распознаваемый МП-автоматом, - множество всех слов, допускаемых этим МП-автоматом. Язык, распознаваемый МП-автоматом M, обозначается L(M).

Замечание 10.1.14.

Обычно в учебниках используется более узкое определение МП-автомата, но это не меняет класса языков, распознаваемых МП-автоматами.




Содержание  Назад  Вперед