Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Автоматы с магазинной памятью
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лекція
Предмет:
Математическая теория формальных языков
Частина тексту файла (без зображень, графіків і формул):
Пентус А.Е. Математическая теория формальных языков. - М.: Изд-во "Интернет-университет информационных технологий - ИНТУИТ.ру", 2006. - 248 c.: ил.
10. Лекция: Автоматы с магазинной памятью
В данной лекции рассматриваются автоматы с магазинной памятью, в которых помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как магазин. Даются необходимые определения, и доказывается, что автоматы с магазинной памятью распознают в точности контекстно-свободные языки. Приведены примеры практического использования автоматов с магазинной памятью и приведены упражнения для самостоятельной проработки
Подобно тому, как праволинейным грамматикам соответствуют конечные автоматы, контекстно-свободным грамматикам соответствуют автоматы с магазинной памятью (МП-автоматы). В таком автомате, помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как стек (магазин), то есть структура данных, где в каждый момент доступен только тот элемент, который был добавлен позже остальных присутствующих на данный момент элементов.
Для наглядности стек обычно изображают вертикально, так, что доступный элемент данных (вершина) находится наверху. Но при формальном определении конфигурации (мгновенного состояния) МП-автомата удобно считать все содержимое стека конечной последовательностью символов, то есть словом (в алфавите, в котором перечислены все возможные данные, "умещающиеся" в одной ячейке стека). Прежде чем определить конфигурацию, придется принять произвольное соглашение о том, в каком порядке записывать содержимое стека в этом слове. В этой книге считается, что вершина стека находится в начале слова (то есть слева). В разделе 10.1 даются необходимые определения. В разделе 10.2 доказывается, что МП-автоматы распознают в точности контекстно-свободные языки.
10.1. Определение автомата с магазинной памятью
Определение 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. Обычно в учебниках используется более узкое определение МП-автомата, но это не меняет класса языков, распознаваемых МП-автоматами.
Пример 10.1.15. Пусть - МП-автомат из примера 10.1.2. Тогда .
Пример 10.1.16. Пусть . Рассмотрим МП-автомат , где , , I = {1}, F = {4,5} и
Тогда .
Определение 10.1.17. Два МП-автомата эквивалентны, если они распознают один и тот же язык.
Замечание 10.1.18. В данном пособии не рассматриваются преобразователи с магазинной памятью (pushdown transducer) обобщение автоматов с магазинной памятью посредством добавления "выходного" потока (см. [7, 3.5] или [2, 3.1.4]).
Замечание 10.1.19. Некоторые авторы изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния и и последовательность , что . Такое определение не изменяет класса языков, распознаваемых МП-автоматами.
Замечание 10.1.20. Некоторые авторы добавляют в определение МП-автомата седьмую компоненту - Z0, называемую маркером магазинной памяти (start pushdown symbol), и изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния и , что . Такое определение не изменяет класса языков, распознаваемых МП-автоматами.
Замечание 10.1.21. Класс языков, распознаваемых МП-автоматами, не изменится также, если использовать следующую естественную комбинацию двух предыдущих определений: слово w допускается МП-автоматом , если найдутся такие состояния и и последовательность , что .
Замечание 10.1.22. Некоторые авторы добавляют в определение МП-автомата маркер магазинной памяти Z0, отбрасывают множество F и изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния и , что . Это также не изменяет класса языков, распознаваемых МП-автоматами.
Упражнение 10.1.23. Найти МП-автомат, распознающий язык
Упражнение 10.1.24. Найти МП-автомат, распознающий язык
Упражнение 10.1.25. Найти МП-автомат, распознающий язык
10.2. Характеризация контекстно-свободных языков
Теорема 10.2.1. Если язык L является контекстно-свободным, то существует МП-автомат, распознающий этот язык.
Доказательство. Пусть язык L порождается контекстно-свободной грамматикой , в которой каждое правило имеет вид , где , и (в силу теоремы 8.8.3 такая грамматика существует). Положим , , , и
Можно доказать, что тогда и только тогда, когда существует левосторонний вывод (здесь и ).
Пример 10.2.2. Пусть . Контекстно-свободная грамматика
и МП-автомат , где
задают один и тот же язык.
Лемма 10.2.3. Каждый МП-автомат эквивалентен некоторому МП-автомату , где |I| = 1, |F| = 1 и каждый переход удовлетворяет требованиям и .
Пример 10.2.4. Рассмотрим МП-автомат , где , , ,
Он эквивалентен МП-автомату , где и
Пример 10.2.5. Рассмотрим МП-автомат , где , , ,
Он эквивалентен МП-автомату , где , и
Пример 10.2.6. Рассмотрим МП-автомат , где , , ,
Он эквивалентен МП-автомату , где , , , ,
Теорема 10.2.7. Если язык L распознается некоторым МП-автоматом, то L является контекстно-свободным.
Доказательство. Пусть язык L распознается МП-автоматом . Без ограничения общности можно считать, что , и каждый переход удовлетворяет требованию . Построим искомую контекстно-свободную грамматику , положив , и
Можно доказать, что тогда и только тогда, когда (здесь ).
Пример 10.2.8. МП-автомат , где , ,
и контекстно-свободная грамматика
задают один и тот же язык. Здесь S, T и U соответствуют символам A1,2, A1,1 и A2,2 из доказательства теоремы 10.2.7.
Упражнение 10.2.9. Найти МП-автомат, распознающий язык, порождаемый грамматикой
Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык
Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык
Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык
10.3*. Автоматы с магазинной памятью с однобуквенными переходами
Теорема 10.3.1. Каждый МП-автомат эквивалентен некоторому МП-автомату , где |Q| = 2 и каждый переход удовлетворяет требованиям |x| = 1, и .
Доказательство. Пусть исходным МП-автоматом распознается контекстно-свободный язык . Согласно теореме 8.4.6 язык порождается некоторой контекстно-свободной грамматикой , в которой каждое правило имеет вид , где , , и . Аналогично тому, как было сделано при доказательстве теоремы 10.2.1, положим , Q = {1,2}, I = {1},
Теорема 10.3.2. Каждый МП-автомат эквивалентен некоторому МП-автомату , в котором каждый переход удовлетворяет требованиям |x| = 1, и .
Доказательство. Пусть исходным МП-автоматом распознается контекстно-вободный язык . Согласно теореме 8.4.6 язык порождается некоторой контекстно-вободной грамматикой , в которой каждое правило имеет один из следующих трех видов: , , , где , , , . Легко добиться того, чтобы в правилах грамматики G вспомогательные символы в правой части (то есть символы B и C) были отличны от начального символа S.
Положим , где . Далее, положим ,
Упражнение 10.3.3. Найти для языка, порождаемого грамматикой
МП-автомат, в котором каждый переход удовлетворяет требованиям |x| = 1, и .
Упражнение 10.3.4. Найти для языка, порождаемого грамматикой
МП-автомат, в котором каждый переход удовлетворяет требованиям , и .
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора