dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 55
Текст из файла (страница 55)
Магазинные символы представлены прописными буквами из конца алфавита, например, X или Y.5. Цепочки магазинных символов обозначаются греческими буквами, например, αили β.6.1. ÎÏÐÅÄÅËÅÍÈÅ ÀÂÒÎÌÀÒÎÂ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞСтр. 239239εεεεεРис. 6.3. Конфигурации МП-автомата из примера 6.2 при входе 1111Для дальнейших рассуждений о МП-автоматах понадобятся следующие три важныхпринципа.1.Если последовательность конфигураций (вычисление) является допустимой (legal)для МП-автомата P (с точки зрения его определения), то вычисление, образованноепутем дописывания одной и той же цепочки к концам входных цепочек всех егоконфигураций, также допустимо.2.Если вычисление допустимо для МП-автомата P, то вычисление, образованное дописыванием одних и тех же магазинных символов внизу магазина в каждой конфигурации, также допустимо.3.Если вычисление допустимо для МП-автомата P, и в результате некоторый суффикс(tail) входной цепочки не прочитан, то вычисление, полученное путем удаления этого суффикса из входных цепочек каждой конфигурации, также допустимо.Интуитивно данные, которые никогда не читаются МП-автоматом, не влияют на его вычисления.
Формализуем приведенные пункты 1 и 2 в виде следующей теоремы.240Стр. 240ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ*Теорема 6.5. Если P = (Q, Σ, Γ, δ, q0, Z0, F) — МП-автомат и (q, x, α) |− (p, y, β), тоPдля любой цепочки w из Σ* и γ из Γ* верно следующее утверждение.*(q, xw, αγ) |− (p, yw, βγ)PЗаметим, что если γ = ε, то получается формальное утверждение приведенного вышепринципа 1, а при w = ε — принципа 2.Доказательство. Доказательство проводится очень просто индукцией по числу шагов в последовательности МО, приводящих (q, xw, αγ) к (p, yw, βγ). Каждый из переходов*в последовательности (q, x, α) |− (p, y, β) обосновывается переходами P без какого-либоPиспользования w и/или γ. Следовательно, каждый переход обоснован и в случае, когдаэти цепочки присутствуют на входе и в магазине.
Заметим, что обращение этой теоремы неверно. Существуют действия, которые МПавтомат мог бы совершить с помощью выталкивания из стека, т.е. используя некоторыесимволы γ и заменяя их в магазине, что невозможно без обработки γ. Однако, как утверждает принцип 3, мы можем удалить неиспользуемый вход, так как МП-автомат не может прочитать входные символы, а затем восстановить их на входе. Сформулируемпринцип 3 следующим образом.Íóæíû ëè êîíôèãóðàöèè êîíå÷íûõ àâòîìàòîâ?Можно было бы удивиться, почему понятие конфигурации не было введено для конечных автоматов. Хотя конечный автомат не имеет магазина, в качестве МО для него можно было бы использовать пару (q, w), где q — состояние, а w — остаток входа.Определить такие конфигурации можно, но их достижимость не дает никакой новой∧информации по сравнению с тем, что давало использование δ .
Иными словами, для∧любого конечного автомата можно показать, что δ (q, w) = p тогда и только тогда,*когда (q, wx) |− (p, x) для всех цепочек x. Тот факт, что x может быть чем угодно, невлияющим на поведение конечного автомата, является теоремой, аналогичной теоремам 6.5 и 6.6.*Теорема 6.6. Если P = (Q, Σ, Γ, δ, q0, Z0, F) — МП-автомат и (q, xw, α) |− (p, yw, β), тоP*верно также, что (q, x, α) |− (p, y, β). P6.1.5.
Óïðàæíåíèÿ ê ðàçäåëó 6.16.1.1.Предположим, что МП-автомат P = ({q, p}, {0, 1}, {Z0, X}, δ, q, Z0, {p}) имеетследующую функцию переходов.1.δ(q, 0, Z0) = {(q, XZ0)}.6.1. ÎÏÐÅÄÅËÅÍÈÅ ÀÂÒÎÌÀÒÎÂ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞСтр. 2412412.δ(q, 0, X) = {(q, XX)}.3.δ(q, 1, X) = {(q, X)}.4.δ(q, ε, X) = {(p, ε)}.5.δ(p, ε, X) = {(p, ε)}.6.δ(p, 1, X) = {(p, XX)}.7.δ(p, 1, Z0) = {(p, ε)}.Приведите все конфигурации, достижимые из начального МО (q, w, Z0), есливходным словом w является:а) 01;б) 0011;в) 010.6.2. ßçûêè ÌÏ-àâòîìàòîâМы предполагали, что МП-автомат допускает свой вход, прочитывая его и достигаязаключительного состояния. Такой подход называется “допуск по заключительному состоянию”. Существует другой способ определения языка МП-автомата, имеющий важные приложения.
Для любого МП-автомата мы можем определить язык, “допускаемыйпо пустому магазину”, т.е. множество цепочек, приводящих МП-автомат в начальнойконфигурации к опустошению магазина.Эти два метода эквивалентны в том смысле, что для языка L найдется МП-автомат,допускающий его по заключительному состоянию тогда и только тогда, когда для L найдется МП-автомат, допускающий его по пустому магазину. Однако для конкретных МПавтоматов языки, допускаемые по заключительному состоянию и по пустому магазину,обычно различны. В этом разделе показывается, как преобразовать МП-автомат, допускающий L по заключительному состоянию, в другой МП-автомат, который допускает Lпо пустому магазину, и наоборот.6.2.1.
Äîïóñòèìîñòü ïî çàêëþ÷èòåëüíîìó ñîñòîÿíèþПусть P = (Q, Σ, Γ, δ, q0, Z0, F) — МП-автомат. Тогда L(P), языком, допускаемым P позаключительному состоянию, является*{w | (q0, w, Z0) |− (q, ε, α)}Pдля некоторого состояния q из F и произвольной магазинной цепочки α. Таким образом,начиная со стартовой конфигурации с w на входе, P прочитывает w и достигает допускающего состояния. Содержимое магазина в этот момент не имеет значения.242Стр. 242ÃËÀÂÀ 6.
ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞПример 6.7. Мы утверждали, что МП-автомат из примера 6.2 допускает язык Lwwr, состоящий из цепочек вида wwR в алфавите {0, 1}. Выясним, почему это утверждение верно.Оно имеет вид “тогда и только тогда, когда”: МП-автомат P из примера 6.2 допускает цепочку x по заключительному состоянию тогда и только тогда, когда x имеет вид wwR.(Достаточность) Эта часть проста; нужно показать лишь допускающее вычислениеP. Если x = wwR, то заметим, что справедливы следующие соотношения.**(q0, wwR, Z0) |− (q0, wR, wRZ0) |− (q1, wR, wRZ0) |− (q1, ε, Z0) |− (q2, ε, Z0)Таким образом, МП-автомат имеет возможность прочитать цепочку w на входе и записать ее символы в свой магазин в обратном порядке.
Затем он спонтанно переходит в состояние q1 и проверяет совпадение wR на входе с такой же цепочкой в магазине, и наконец, спонтанно переходит в состояние q2.(Необходимость) Эта часть труднее. Во-первых, заметим, что единственный путьдостижения состояния q2 состоит в том, чтобы находиться в состоянии q1 и иметь Z0 навершине магазина.
Кроме того, любое допускающее вычисление P начинается в состоянии q0, совершает один переход в q1 и никогда не возвращается в q0. Таким образом, дос*таточно найти условия, налагаемые на x, для которых (q0, x, Z0) |− (q1, ε, Z0); именно такие цепочки и допускает P по заключительному состоянию. Покажем индукцией по |x|следующее несколько более общее утверждение.*• Если (q0, x, α) |− (q1, ε, α), то x имеет вид wwR.Базис. Если x = ε, то x имеет вид wwR, с w = ε.
Таким образом, заключение верно, иутверждение истинно. Отметим, что нам не обязательно доказывать истинность гипотезы*(q0, ε, α) |− (q1, ε, α), хотя она и верна.Индукция. Пусть x = a1a2…an для некоторого n > 0. Существуют следующие два перехода, которые P может совершить из МО (q0, x, α).1.(q0, x, α) |− (q1, x, α). Теперь P может только выталкивать из магазина, находясь всостоянии q1.
P должен вытолкнуть символ из магазина с чтением каждого входного*символа, и |x| > 0. Таким образом, если (q1, x, α) |− (q1, ε, β), то цепочка β короче,чем α, и не может ей равняться.2.(q0, a1a2…an, α) |− (q0, a2…an, a1α). Теперь последовательность переходов может закончиться в (q1, ε, α), только если последний переход является следующим выталкиванием.(q1, an, a1α) |− (q1, ε, α)В этом случае должно выполняться a1 = an. Нам также известно, что*(q0, a2…an, a1α) |− (q1, an, a1α)6.2.
ßÇÛÊÈ ÌÏ-ÀÂÒÎÌÀÒÎÂСтр. 243243По теореме 6.6 символ an можно удалить из конца входа, поскольку он не используется. Тогда*(q0, a2…an–1, a1α) |− (q1, ε, a1α)Поскольку вход у этой последовательности короче, чем n, можно применить индуктивное предположение и заключить, что a2…an–1 имеет вид yyR для некоторого y.Поскольку x = a1yyRan, и нам известно, что a1 = an, делаем вывод, что x имеет видwwR; в частности w = a1y.Приведенные рассуждения составляют сердцевину доказательства того, что x допускается только тогда, когда равен wwR для некоторого w. Таким образом, необходимостьдоказана. Вместе с достаточностью, доказанной ранее, она гласит, что P допускает вточности цепочки из Lwwr. 6.2.2.
Äîïóñòèìîñòü ïî ïóñòîìó ìàãàçèíóДля каждого МП-автомата P = (Q, Σ, Γ, δ, q0, Z0, F) определим*N(P) = {w | (q0, w, Z0) |− (q, ε, ε)},где q — произвольное состояние. Таким образом, N(P) представляет собой множествовходов w, которые P может прочитать, одновременно опустошив свой магазин.2Пример 6.8. МП-автомат P из примера 6.2 никогда не опустошает свой магазин, поэтому N(P) = ∅. Однако небольшое изменение позволит автомату P допускать Lwwr какпо пустому магазину, так и по заключительному состоянию.
Вместо переходаδ(q1, ε, Z0) ={(q2, Z0)} используем δ(q1, ε, Z0) = {(q2, ε)}. Теперь P выталкивает последний символ измагазина, когда допускает, поэтому L(P) = N(P) = Lwwr. Поскольку множество допускающих состояний не имеет значения, иногда в случаях,когда нас будет интересовать допуск только по пустому магазину, будем записыватьМП-автомат в виде шестерки (Q, Σ, Γ, δ, q0, Z0), опуская седьмой компонент.6.2.3. Îò ïóñòîãî ìàãàçèíà ê çàêëþ÷èòåëüíîìó ñîñòîÿíèþПокажем, что классы языков, допускаемых МП-автоматами по заключительному состоянию и по пустому магазину, совпадают. В разделе 6.3 будет доказано, что МПавтоматы определяют КС-языки. Наша первая конструкция показывает, как, исходя изМП-автомата PN, допускающего язык L по пустому магазину, построить МП-автомат PF,допускающий L по заключительному состоянию.Теорема 6.9.
Если L = N(PN) для некоторого МП-автомата PN = (Q, Σ, Γ, δN, q0, Z0), тосуществует такой МП-автомат PF, у которого L = L(PF).2244Стр. 244Символ N в N(P) обозначает “пустой магазин” (“null stack”).ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞДоказательство. Идея доказательства представлена на рис. 6.4. Используется новыйсимвол X0, который не должен быть элементом Γ; X0 является как стартовым символомавтомата PF, так и маркером дна магазина, позволяющим узнать, когда PN опустошаетмагазин. Таким образом, если PF обозревает X0 на вершине магазина, то он знает, что PNопустошает свой магазин на этом же входе.εεεНачалоεεεεεεРис.
6.4. PF имитирует PN и допускает, если PN опустошает свой магазинНам нужно также новое начальное состояние p0, единственной функцией которогоявляется затолкнуть Z0, стартовый символ автомата PN, на вершину магазина и перейти всостояние q0, начальное для PN. Далее PF имитирует PN до тех пор, пока магазин PN нестанет пустым, что PF определяет по символу X0 на вершине своего магазина. И наконец,нужно еще одно новое состояние pf, заключительное в автомате PF; он переходит в pf, кактолько обнаруживает, что PN опустошает свой магазин.Описание PF имеет следующий вид.PF = (Q U {p0, pf}, Σ, Γ U {X0}, δF, p0, X0, {pf})Функция δF определяется таким образом.1.δF(p0, ε, X0) = {(q0, Z0X0)}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
