Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 54
Текст из файла (страница 54)
д„: начальное состояние. МП-автомат находится в нем перед началом работы. Щ начальный магазинный символ ("маркер дна'*). Вначале магазин содержит только этот символ и ничего более. Е множество допускающих, или заключительных, состояний. Никаких "смешиваний и сочетаний" В некоторых случаях МП-автомат может иметь несколько пар на выбор. Например, пусть б(д, а,Х) = ((р, У2), (г, е)).
Совершая переход, автомат должен выбрать пару целиком, т.е. нельзя взять состояние из одной пары, а цепочку для замещения в магазине — из другой. Таким образом, имея состояние д, символ Х на вершине магазина и а на входе, автомат может либо перейти в состояние р и изменить Х на У7, перейти либо в г и вытолкнуть Х. Однако перейти в состояние р и вытолкнуть Х или перейти в г и изменить Х на У7 нельзя. Пример 6.2. Построим МП-автомат Р, допускающий язык У.„„, нз примера 6.1.
Вначале уточним одну деталь, необходимую для правильной организации работы с магазином. Магазинный символ 70 используется для отметки дна магазина. Этот символ должен присутствовать в магазине, чтобы, удалив из магазина зг и обнаружив на входе ви, можно было совершить переход в допускающее состояние д,. Итак, наш МП-автомат для языка у.„,„,, можно представить в следующем виде. Р = ((до, дь дэ), (О, 1), (О, 1, 7о), б, до, 7о, (дЛ) Функция 6 определяется такими правилами. ! о(дь 0 70) = ((да, 07а)) и б(дм 1, 7,) = ((дь 170)). Одно из этих правил применяется вначале, когда автомат находится в состоянии да и обозревает начальный символ 7а на вершине магазина.
Читается первый символ и помещается в магазин;?, остается под ним для отметки дна. 2 б(до 0 0) = ((да,00)) фдо 0 !) = ((да, 01)), фдо,!,0)= ((да,10)) и Тдо, 1 !)= ((д„11)). Эти четыре аналогичные правила позволяют оставаться в состоянии д0 и читать входные символы, помещая каждый из них на вершину магазина над предыдущим верхним символом. 3. Г(до, в,7о) = ((дь7о)), б(де цО) = ИдьО)) и б(де к, 1)= ((до 1)).
Эти пРавила позволяют автомату спонтанно (без чтения входа) переходить из состояния д, в состояние дь не изменяя верхний символ магазина, каким бы он ни был. ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 236 4 4Ч(, б, б) = НЖ, я)) и 4е(о 1, 1) = Пе((, е)). В состоянии а(( входные символы проверяются на совпадение с символами на вершине магазина. При совпадении последние вытаякиваются.
4Ч(, а 2а) = 11((л 2а)). Наконеп, если обнаРУжен маРкеР дна магазина 2а и автомат находится в состоянии е((, то обнаружен вход вида аваек. Автомат переходит в со- стояние е(а и допускает. 6.1.3. Графическое представление МП-автоматов Функпшо 4 заданную списком, как в примере 6.2, отследить нелегко.
Иногда особенности повеления МП-автомата становятся более понятными по диаграмме, обобшаюшей диаграмму переходов конечного автомата. Введем в рассмотрение и используем в дальнейшем дилер(лимы переходов МП-автоматов со следующими свойствами. 1. Вершины соответствуют состояниям МП-автомата. Стрелка, отмеченная словом Начало, указывает на начальное состояние, а обведенные двойным кружком состояния являются заключительными, как и у конеч- ных автоматов. вершине магазина.
Диаграмма не говорит лишь о том, какой магазинный символ является стартовым. По со- глашению им будет Еа, если не оговаривается иное. О,х,(ОЛ, 0,0(ОО 0,1(О1 1,О(1О 1,1(11 о,о(е 1,1(е Начал е, ла(ла е, о(о е, 1(! Рис. 6.2 Представление МП-автомата в виде обобщенной диаграммы переходов Пример 6З.
МП-автомат из примера 6,2 представлен в виде диаграммы на рис. 6.2. П 6.1. ОПРЕДЕЛЕНИЕ АВТОМАТОВ С МАГАЗИННОЙ ПАМЯТЬЮ 237 3. Дуги соответствуют переходам МП-автомата в следуюшем смысле. Дуга, отмеченная а, Х(а и ведушая из состояния е( в состояние р, означает, что 4е(, а, Х) содержит пару 1р, а) (возможно, и другие пары). Таким образом, отметка дуги показывает, какой входной символ используется, а также, что было и что будет на 6.1.4. Конфигурации МП-автомата Сейчас у нас есть лишь неформальное понятие того, как МП-автомат "вычисляет". Интуитивно МП-автомат переходит от конфигурации к конфигурации в соответствии с входными символами (или е), но в отличие от конечного автомата, о котором известно только его состояние, конфигурация МП-автомата включает как состояние, так и содержимое магазина.
Поскольку магазин может быть очень большим, он часто является наиболее важной частью конфигурации. Полезно также представлять в качестве части конфигурации непрочитанную часть входа. Таким образом, конфигурация МП-автомата представляется тройкой (д, гг, у), где д— состояние, и — оставшаяся часть входа, у — содержимое магазина. По соглашению вершина магазина изображается слева, а дно — справа. Такая тройка называется конфигурацией МП-автомата, или его яггновенным описанием, сокращенно МО (1пзгапгапеоцз г1езспрйоп — П)).
Поскольку МО конечного автомата — зто просто его состояние, для представления последовательностей конфигураций, через которые он проходил, было достаточно использовать б . Однако для МП-автоматов нужна нотация, описывающая изменения состояния, входа и магазина. Таким образом, используются пары конфигураций, связи между которыми представляют переходы МП-автомата. Пусть Р = (Д, Х, Г, 4 д», Д, Р') — МП-автомат. Определим отношение Г-, или просто Р ~ —, когда Р подразумевается, следующим образом.
Предположим, что о(ц, а, Х) содержит (р, а). Тогдадля всех цепочек и изХ и)3из Г полагаем(д, аи,Х1З) )- (Р, зг, а)З). Этот переход отражает идею того, что, прочитывая на входе символ а, который может быть е, и заменяя Х на вершине магазина цепочкой а, можно перейти из состояния д в состояние р. Заметим, что оставшаяся часть входа (н) и содержимое магазина под его вершиной (Щ не влияют на действие МП-автомата; они просто сохраняются, возможно, для того, чтобы влиять на события в дальнейшем. Используем также символ ~-, или просто ~-, когда МП-автомат Р подразумевается, для представления нуля или нескольких переходов МП-автомата.
Итак, имеем следую- шее индуктивное определение. Базис.! ~- 1для любого МО й Индукцня. 1 )- l, если существует некоторое МО К, удовлетворяющее условиям ()-КиК)-Х Таким образом, 1 ~- У, если существует такая последовательность МО Кн К,, ..., К„, у которой 1 = Кь .У = К„и К, ~- Кьо для всех 1 = 1, 2, ..., п — 1. 238 ГЛАВА б. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Пример 6.4. Рассмотрим работу МП-автомата из примера 6.2 со входом 11!1. Поскольку ~)а — начальное состояние, а ?а — стартовый символ, то начальным МО будет (4в 11! 1,?а).
На этом входе МП-автомат имеет возможность несколько раз делать ошибочные предположения. Вся последовательность МО, достижимых из начальной конфигурации, показана на рис. 6.3. Стрелки представляют отношение )-. Из начального МО можно выбрать два перехода. Первый предполагает, что середина не достигнута и ведет к МО (д„, 111, 1?0). В результате символ 1 перемещается а магазин. Второй выбор основан на предположении, что достигнута середина входа. Без прочитывания очередного символа МП-автомат переходит в состояние дь что приводит к МО ф, 11!1, ?0).
Поскольку МП-автомат может допустить вход, если он находится в состоянии д, и обозревает ?» на вершине магазина, он переходит к МО (дл 1111, 7„). Это МО не является в точности допускающим, так как вход не дочитан до конца. Если бы входом вместо 111! было а, то та же самая последовательность переходов привела к МО (дв а ?с), показывающему, что а допущено. МП-автомат может также предположить, что он увидел середину после чтения первой 1, т.е. находясь в конфигурации (()ж 111, 1?0). Это предположение также ведет к ошибке, поскольку вход не может быть дочитан до конца. Правильное предположение, что середина достигается после прочтения 11, дает последовательность МО (с)а, 11)1,?а) )- (дь 1)1, 1?а) )- (с)о, 11,! 1?о) )- (г)ь 11 1!?о) )- (дь 1, 1?о) ) — (д! е 70) )- (г)д К ?о).
С) Соглашения по записи МП-автовтатов Продолжим соглашения об использовании символов, введенные для конечных автоматов и грамматик. Придерживаясь системы записи, полезно представлять себе, что магазинные символы играют роль, аналогичную объединению терминалов и переменных в КС-грамматиках. 1. Символы входного алфавита представлены строчными буквами из начала алфавита, например, а или Ь. 2. Состояния обычно представляются буквами р и г( или другими, близкими к ним в алфавитном порядке.
3. Цепочки входных символов обозначаются строчными буквами из конца алфавита, например, и или -. 4. Магазинные символы представлены прописными буквами из конца алфавита, например, Хили К 5. Цепочки магазинных символов обозначаются греческими буквами, например, а или )3. 6.1. ОПРЕДЕЛЕНИЕ АВТОМАТОВ С МАГАЗИННОЙ ПАМЯТЬЮ 239 (Ч,,Ш,(2 ) (Ч,,ПП,2,) — В (Чг,иц,2 ) (»,,ц,пд,) (ч,,ш,)2«) — «-(» и 2«) (Ч~ е ° (П)2«) (Ч~ е П2«) (Ч1 ° е 2«) Рис. б 3. Конфигурации МПавтомата из примера 6 2 при входе ! ! ! ! Для дальнейших рассуждений о МП-автоматах понадобятся следующие три важных принципа. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
