dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 54
Текст из файла (страница 54)
Вначале магазин содержит толькоэтот символ и ничего более.F: множество допускающих, или заключительных, состояний.Íèêàêèõ “ñìåøèâàíèé è ñî÷åòàíèé”В некоторых случаях МП-автомат может иметь несколько пар на выбор. Например,пусть δ(q, a, X) = {(p, YZ), (r, ε)}. Совершая переход, автомат должен выбрать паруцеликом, т.е. нельзя взять состояние из одной пары, а цепочку для замещения в магазине — из другой. Таким образом, имея состояние q, символ X на вершине магазина иa на входе, автомат может либо перейти в состояние p и изменить X на YZ, перейтилибо в r и вытолкнуть X.
Однако перейти в состояние p и вытолкнуть X или перейти вr и изменить X на YZ нельзя.Пример 6.2. Построим МП-автомат P, допускающий язык Lwwr из примера 6.1. Вначале уточним одну деталь, необходимую для правильной организации работы с магазином. Магазинный символ Z0 используется для отметки дна магазина. Этот символ должен присутствовать в магазине, чтобы, удалив из магазина w и обнаружив на входе wwR,можно было совершить переход в допускающее состояние q2. Итак, наш МП-автомат дляязыка Lwwr можно представить в следующем виде.P = ({q0, q1, q2}, {0, 1}, {0, 1, Z0}, δ, q0, Z0, {q2})Функция δ определяется такими правилами.1.δ(q0, 0, Z0) = {(q0, 0Z0)} и δ(q0, 1, Z0) = {(q0, 1Z0)}. Одно из этих правил применяетсявначале, когда автомат находится в состоянии q0 и обозревает начальный символ Z0на вершине магазина. Читается первый символ и помещается в магазин; Z0 остаетсяпод ним для отметки дна.2.236Стр.
236δ(q0, 0, 0) = {(q0, 00)}, δ(q0, 0, 1) = {(q0, 01)}, δ(q0, 1, 0) = {(q0, 10)} и δ(q0, 1, 1) ={(q0, 11)}. Эти четыре аналогичные правила позволяют оставаться в состоянии q0 ичитать входные символы, помещая каждый из них на вершину магазина над предыдущим верхним символом.ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ3.δ(q0, ε, Z0) = {(q1, Z0)}, δ(q0, ε, 0) = {(q1, 0)} и δ(q0, ε, 1) = {(q1, 1)}. Эти правила позволяют автомату спонтанно (без чтения входа) переходить из состояния q0 в состояние q1, не изменяя верхний символ магазина, каким бы он ни был.4.δ(q1, 0, 0) = {(q1, ε)} и δ(q1, 1, 1) = {(q1, ε)}. В состоянии q1 входные символы проверяются на совпадение с символами на вершине магазина. При совпадении последниевыталкиваются.5.δ(q1, ε, Z0) = {(q2, Z0)}.
Наконец, если обнаружен маркер дна магазина Z0 и автоматнаходится в состоянии q1, то обнаружен вход вида wwR. Автомат переходит в состояние q2 и допускает.6.1.3. Ãðàôè÷åñêîå ïðåäñòàâëåíèå ÌÏ-àâòîìàòîâФункцию δ, заданную списком, как в примере 6.2, отследить нелегко. Иногда особенности поведения МП-автомата становятся более понятными по диаграмме, обобщающейдиаграмму переходов конечного автомата. Введем в рассмотрение и используем в дальнейшем диаграммы переходов МП-автоматов со следующими свойствами.1.Вершины соответствуют состояниям МП-автомата.2.Стрелка, отмеченная словом Начало, указывает на начальное состояние, а обведенные двойным кружком состояния являются заключительными, как и у конечных автоматов.3.Дуги соответствуют переходам МП-автомата в следующем смысле.
Дуга, отмеченная a, X/α и ведущая из состояния q в состояние p, означает, что δ(q, a, X) содержит пару (p, α) (возможно, и другие пары). Таким образом, отметка дуги показывает, какой входной символ используется, а также, что было и что будет навершине магазина.Диаграмма не говорит лишь о том, какой магазинный символ является стартовым. По соглашению им будет Z0, если не оговаривается иное.εεНачалоε,ε,ε,ε,Рис. 6.2.
Представление МП-автомата в виде обобщенной диаграммы переходов6.1. ÎÏÐÅÄÅËÅÍÈÅ ÀÂÒÎÌÀÒÎÂ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞСтр. 237237Пример 6.3. МП-автомат из примера 6.2 представлен в виде диаграммы на рис. 6.2. 6.1.4. Êîíôèãóðàöèè ÌÏ-àâòîìàòàСейчас у нас есть лишь неформальное понятие того, как МП-автомат “вычисляет”.Интуитивно МП-автомат переходит от конфигурации к конфигурации в соответствии свходными символами (или ε), но в отличие от конечного автомата, о котором известнотолько его состояние, конфигурация МП-автомата включает как состояние, так и содержимое магазина. Поскольку магазин может быть очень большим, он часто является наиболее важной частью конфигурации.
Полезно также представлять в качестве части конфигурации непрочитанную часть входа.Таким образом, конфигурация МП-автомата представляется тройкой (q, w, γ), где q —состояние, w — оставшаяся часть входа, γ — содержимое магазина. По соглашениювершина магазина изображается слева, а дно — справа. Такая тройка называется конфигурацией МП-автомата, или его мгновенным описанием, сокращенно МО (instantaneousdescription — ID).Поскольку МО конечного автомата — это просто его состояние, для представленияпоследовательностей конфигураций, через которые он проходил, было достаточно ис∧пользовать δ .
Однако для МП-автоматов нужна нотация, описывающая изменения состояния, входа и магазина. Таким образом, используются пары конфигураций, связи между которыми представляют переходы МП-автомата.Пусть P = (Q, Σ, Γ, δ, q0, Z0, F) — МП-автомат. Определим отношение |− , или простоP|− , когда P подразумевается, следующим образом.
Предположим, что δ(q, a, X) содержит(p, α). Тогда для всех цепочек w из Σ* и β из Γ* полагаем (q, aw, Xβ) |− (p, w, αβ).Этот переход отражает идею того, что, прочитывая на входе символ a, который может быть ε, и заменяя X на вершине магазина цепочкой α, можно перейти из состояния qв состояние p. Заметим, что оставшаяся часть входа (w) и содержимое магазина под еговершиной (β) не влияют на действие МП-автомата; они просто сохраняются, возможно,для того, чтобы влиять на события в дальнейшем.**Используем также символ |− , или просто |− , когда МП-автомат P подразумевается,Pдля представления нуля или нескольких переходов МП-автомата.
Итак, имеем следующее индуктивное определение.*Базис. I |− I для любого МО I.*Индукция. I |− J, если существует некоторое МО K, удовлетворяющее условиям*I |− K и K |− J.238Стр. 238ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ*Таким образом, I |− J, если существует такая последовательность МО K1, K2, …, Kn, у которой I = K1, J = Kn, и Ki |− Ki+1 для всех i = 1, 2, …, n – 1.Пример 6.4. Рассмотрим работу МП-автомата из примера 6.2 со входом 1111. Поскольку q0 — начальное состояние, а Z0 — стартовый символ, то начальным МО будет(q0, 1111, Z0). На этом входе МП-автомат имеет возможность несколько раз делать ошибочные предположения. Вся последовательность МО, достижимых из начальной конфигурации, показана на рис.
6.3. Стрелки представляют отношение |− .Из начального МО можно выбрать два перехода. Первый предполагает, что середина не достигнута и ведет к МО (q0, 111, 1Z0). В результате символ 1 перемещаетсяв магазин.Второй выбор основан на предположении, что достигнута середина входа. Без прочитывания очередного символа МП-автомат переходит в состояние q1, что приводит к МО(q1, 1111, Z0). Поскольку МП-автомат может допустить вход, если он находится в состоянии q1 и обозревает Z0 на вершине магазина, он переходит к МО (q2, 1111, Z0).
ЭтоМО не является в точности допускающим, так как вход не дочитан до конца. Если бывходом вместо 1111 было ε, то та же самая последовательность переходов привела к МО(q0, ε, Z0), показывающему, что ε допущено.МП-автомат может также предположить, что он увидел середину после чтения первой 1, т.е. находясь в конфигурации (q0, 111, 1Z0). Это предположение также ведет к ошибке, поскольку вход не может быть дочитан до конца. Правильное предположение, что середина достигается после прочтения 11, дает последовательность МО (q0, 1111, Z0) |−(q0, 111, 1Z0) |− (q0, 11, 11Z0) |− (q1, 11, 11Z0) |− (q1, 1, 1Z0) |− (q1, ε, Z0) |− (q2, ε, Z0).
Ñîãëàøåíèÿ ïî çàïèñè ÌÏ-àâòîìàòîâПродолжим соглашения об использовании символов, введенные для конечных автоматов и грамматик. Придерживаясь системы записи, полезно представлять себе, чтомагазинные символы играют роль, аналогичную объединению терминалов и переменных в КС-грамматиках.1. Символы входного алфавита представлены строчными буквами из начала алфавита, например, a или b.2. Состояния обычно представляются буквами p и q или другими, близкими к ним валфавитном порядке.3. Цепочки входных символов обозначаются строчными буквами из конца алфавита,например, w или z.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
