1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 76
Текст из файла (страница 76)
В некотором смысле каждая поверхностная конфигурация представляет многие МΠ— те, у которых "поверхность", т. е. вершина магазина, совпадает с третьей компонентой згв В.Е ДВУСТОРОННИЙ ДНА этой конфигурации. Говорят, что конфигурация С'=(з', 1', А) выводима из конфигурации С=(з, 1, А), и пишут С ~ С', если найдется такая последовательность шагов автомата Р, что при т= О С) — (з„(„а,) )- (з„1„а,) ) — (з, 1„, а„) )- С', где ~а; ~)2 для каждого 1 '). В этой последовательности шагов промежуточные МО (зь 1н сзт) имеют в магазине не менее двух символов.
Мы будем оперировать с конфигурациями, а не с МО, потому что конфигураций только 0(п), а число различных МО может быть экспоненциальным. Определение, Конфигурацию (з, 1, А) называют терминальнои, если значение 6(з, а,, А) не определено или имеет вид (з', й, рор). Иными словами, терминальная конфигурация приводит или к остановке автомата Р, или к удалению символа из магазина. Терминатором конфигурации С называется такая единственная терминальная конфигурация С' (если она существует), что С=,-'>* С', где ~' — рефлексивное и транзитивиое замыкание отношения ~, Пример 9.13.
Если изобразить длину магазинного списка как функцию числа шагов, сделанных автоматом Р, можно получить кривую типа кривой на рис. 9.17. На этом рисунке каждая точка помечена конфигурацией (не МО) автомата Р после каждого шага, Из рис. 9.17 видно, например, что в конфигурациях С, и С„ в вершине стека находится г,. Поскольку между этими конфигурациями нет конфигурации сг, в вершине стека, то С, =оСУН Если Снв заключительная конфигурация, то С„служит терминатором как для себя, так и для С,.
Из этого рисунка можно также вывести, что С, ==;> С„С, =о С„С, =о* С„и ф— терминальная конфигурация, поскольку она приводит к тому, что Р удаляет символ из магазина. П Ключевые соображения для алгоритма моделирования содержатся в следующих двух простых леммах. Лемма 9.1. Р допускает ш тогда и только тогда, когда некоторая конфигурация вида (зь 1, г,), 0 ~1( ~в~+1, служит терминатором начальной конфигурации (з„1, г,,). Д о к а з а т ел ь с т в о. Результат вытекает прямо из определения того, что значит "2ДМА допускает входную цепочку". Е) е) сслн т=о, го с 1 — с'. зтэ гл. а.
алгогнтмы идентификации иселе огана Рис. 9.17. Последоватсльвость конфигураций. Определение. Конфигурацию С назь1вают предшественницей конфигурации О, если С=э О, и непосредственной предшественницей для О, если С~ Р. Говорят, что пара конфигураций (С, О) лежит ниже пары (С', 0') (необязательно различных) конфигураций, если (!) С=(е, 1, А), 0=(1, 1, А), (2) С'=(з', 1', В), Р'=(1', 1', В), (3) (е, 1, А) ) — (е', 1', ВА), (4) (1', 1', ВА) )- (1, 1, А), т. е.
если Р может дойти из С в С' с помощью шага риза, а из 0' в О с помощью шага рор. Лемма 9.2. Если (С, О) лежит ниже (С', 0') и С' ~а О', то С=ф Р. До к аз а тел ьс та о. Легкое упражнение. П Пример 9.14, На рис. 9.17 пара (С„С,) лежит ниже пары (С4, Са), а (фф) — ниже (С„С,). Но нельзя сказать с уверенностью, что (С„С,а) лежит ниже (С„С,), поскольку символы в вершинах магазинов для С, и С, могут быть различными.
П Работа моделирующего алгоритма основана на поиске терминатора для каждой конфигурации 2ДМА Р прн входе ге. Как только найден терминатор начальной конфигурации (е„1, оа), цель достигнута. Для хранения терминатора каждой конфигурации используется массив, называемый ТЕРМ. Мы предполагаем, что множество конфигураций линейно упорядочено (с помощью каких-то лексикографнческих условий). Тогда можно обращаться с именем С конфигурации как с целым числом и считать ТЕРМ(С] терминатором для С. Используется также массив списков ПРЕД. Он индексируется конфигурациями, и ПРЕД[0) — список конфигураций С, для которых С=ф О. Кроме массивов ТЕРМ и ПРЕД используются два дополнительных списка НОВ и ВРЕМ.
Список НОВ содержит пары еще не рас- заа к4. Двустоуонний дмл смотренных конфигураций (С, О), для которых ТЕРМ[С]=О. Список ВРЕМ нужен в процедуре КОРРЕКТИР(С, О), чтобы хранить предшественниц конфигурации С. Мы поступаем следующим образом. Сначала полагаем ТЕРМ[С1= =С, если С вЂ” терминальная конфигурация. (Каждая терминальная конфигурация является своим терминатором.) Добавляем (С, С) к НОВ, Затем рассматриваем такие пары (С, О), что С[ — О за один шаг работы Р.
(Заметим, что при таком шаге магазин не меняется,) Если терминатор для О уже известен, полагаем ТЕРМ[Е1= =ТЕРМ[О] для всех Е, о которых в этот момент известно, что они— предшественницы конфигурации С, включая саму С. (Собственные предшественницы находятся в ПРЕД[С].) Добавляем также пару (Е, ТЕРМ[О]) к списку НОВ. Если терминатор для О еше не известен, то С помещается в ПРЕД[О], т. е. в список непосредственных предшественниц конфигурации О. В этот момент для каждой конфигурации С известна такая единственная конфигурация О, что С=~>" О без изменения магазина, и либо Π— терминатор для С, либо О [ — (з, 1, а) при [а[=2. Теперь рассматриваем все пары конфигураций, уже добавленные к списку НОВ.
В общем случае НОВ содержит нерассмотренные пары конфигураций (А, В), в которых А =~" В и В терминальна. Допустим, что НОВ содержит пару (А, В). Удаляем (А, В) нз НОВ и рассматриваем все пары (С, О) конфигураций, лежащих ниже (А, В). Если терминатор для О уже вычислен, полагаем ТЕРМ[С)=ТЕРМ[О] и добавляем к списку НОВ пару (С, ТЕРМ[О]). Для каждой конфигурации Е из ПРЕД1С1 полагаем ТЕРМ[Е)=ТЕРМ[О) и добавляем (Е, ТЕРМ[О)) к списку НОВ. Но если терминатор для О еше не вычислен, помещаем С в список ПРЕД[О). Продолжаем эту процедуру, пока НОВ не опустеет. В этот момент найден терминатор (если он существует) для каждой конфигурации С. Исчерпав весь список НОВ, рассматриваем ТЕРМ1С,], где С,— начальная конфигурация. Если ТЕРМ[Се[ — допускакицая конфигурация, то 2ДМА Р допускает и. В противном случае Р отвергает в.
Дадим более точное описание. Алгоритм 9.4. Моделирование 2ДМА Вход. 2ДМА Р=(Б, ), Т, б, з„2„е~) и входная цепочка шЕ Р, [ш[=п. Выход. Ответ "да", если в Е 7 (Р), и "нет" в противном случае. Метод. 1. Произведем начальную загрузку массивов и списков следующим образом. Для каждой конфигурации С положим ТЕРМ[С)=И и ПРЕД[С[=Я. Положим НОВ=Я и ВРЕМ=а. звз Гл 9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ ргоседпге КОРРЕКТИР (С, О): Ьеи[п сопипеп1 Всякий раз, когда вызывается КОРРЕКТИР(С,0), имеем С=рО; П ТЕРМ)Р1= Я (Ьеп добавить С к ПРЕД[Я е!ае Ьей[п ВРЕМ вЂ” (С); 99ЬПе ВРЕМФЯ до Ьей[п выбрать и удалить конфигурацию В из ВРЕМ; ТЕРМ(В] — ТЕРМ [Щ добавить (В, ТЕРМ[В)) к НОВ; 1ог А Е ПРЕД['В) до добавить А к ВРЕМ епд епд епд 4.
5. 6. 7. Рис. 838. Процедура КОРРЕКТИР. 2. Для каждой терминальной конфигурации С полагаем ТЕРМ[С)=С и добавляем к НОВ пару (С, С). 3. Для каждой конфигурации С проверяем, существует ли такая конфигурация А1, что С 1 — 1А за один шаг. Если да, вызываем КОРРЕКТИР(С, 17). Процедура КОРРЕКТИР приведена на рис. 9.18. 4. Пока список НОВ не пуст, удаляем пару (С', А)') из НОВ. Для каждой пары (С, Р), лежащей ниже (С', Ау'), вызываем КОРРЕКТИР(С, А1). 5.
Если ТЕРМ[Со), где С, — начальная конфигурация, является заключительной конфигурацией, получаем ответ ода". В противном случае "нет", П Пример 9.15. Рассмотрим некоторые вычисления, выполняемые алгоритмом 9.4, когда он применяется к 2ДМА, работающему, как показано на рис.
9.17. На шаге 2 обнаруживаем, что ффффн Сц — терминальные конфигурации и потому свои же терминаторы. Добавляем к НОВ пары (Со, Со), (Со, Со), (Со, Со), (Сооо Соо) и (Си~ Сн). На шаге 3 вызываем КОРРЕКТИР(С„С,). Поскольку в этот момент ТЕРМ[С,1 = 8, то КОРРЕ КТИР всего лишь помещает С, в список ПРЕД[С,1. На шаге 3 вызываем также КОРРЕКТИР(С,„С,). Так как ТЕРМ[С91=Со, то КОРРЕКТИР полагает ТЕРМ[С,1=С, ел.
двтстопоннии дмл и добавляет (С„С,) к НОВ. Кроме того, на шаге 3 вызываем КОРРЕКТИР(С„С,), и этот вызов полагает ТЕРМ[С,]=С, и добавляет (С„С,) к ЙОВ. Поэтому после шага 3 НОВ содержит пары (С„С,), (С., С,), (фф), (Спо С„), (Сы, С„), (С„С.), (С„С,). На шаге 4 удаляем (С„С,) из НОВ и вызываем КОРРЕКТИР(С„С,), поскольку (С„С,) лежит ниже (С„С,).
Поскольку в этот момент ТЕРМ[Се1=Се, КОРРЕКТИР полагает ТЕРМ[С,]=С, и добавляет (С„С,) к НОВ. Затем на шаге 4 удаляем (С,, С,) из ЙОВ и, поскольку (предположим, что это так) ниже (С„С,) не лежит никакая пара, не вызываем КОРРЕКТИР '). Аналогично не вызываем КОРРЕКТИР для пар (С, С,), (Сыя С„), (Сты С„) и (С„С,). Когда (С„С,) удаляется из ]тОВ, вызываем КОРРЕКТИР(фф), и этот вызов полагает ТЕРМ[С,!=С„и добавляет (фф) к НОВ. В этот момент НОВ содержит (С„С,) и (фф). Удалив (С„С,) из НОВ, вызываем КОРРЕКТИР(С„Ст), что приводит к ТЕРМ[Се] С„и ТЕРМ[Ст1=Сам поскольку ПРЕД[С,] содержит С,. Добавляем (фф) и (фф) к НОВ. Предлагаем читателю завершить это моделирование. С] Теорема 9.10.
Алгоритм 9.4 правильно отвечает на вопрос "Принадлежит ли слово ш язьису Е(Р)?" за время 0([гв[). Д о к а з а т ел ь с т в о. Можно показать, что каждая конфигурация попадает в список ВРЕМ не более одного раза. Поэтому каждый вызов процедуры КОРРЕКТИР закончится. Также можно показать, что никакая пара конфигураций не попадает в список НОВ более одного раза, следовательно, и сам алгоритм закончит работу. Подробное доказательство этих двух утверждений оставляем в качестве упражнения. Покажем, что по окончании работы алгоритма 9.4 ТЕРМ[С,] будет заключительной конфигурацией тогда и только тогда, когда гп Е Е(Р).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
