dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 21
Текст из файла (страница 21)
Ине важно, что в состояние 6 можно попасть из состояния 1, следуя также по пути1→4→5→6, в котором присутствует не ε -переход. Существования одного пути, отмеченного только ε , уже достаточно для того, чтобы состояние 6 содержалось вECLOSE(1). 92Стр. 92ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ2.5.4. Ðàñøèðåííûå ïåðåõîäû è ÿçûêè ε-ÍÊÀС помощью ε-замыкания легко объяснить, как будут выглядеть переходы ε-НКА длязаданной последовательности входных (не-ε) символов.
Исходя из этого, можно определить, что означает для ε-НКА допустимость входных данных.Пусть E = (Q, Σ, δ, q0, F) — некоторый ε-НКА. Для отображения того, что происходит∧при чтении некоторой последовательности символов, сначала определим δ — расши∧ренную функцию переходов. Замысел таков: определить δ (q, w) как множество состояний, в которые можно попасть по путям, конкантенации меток вдоль которых дают цепочку w. При этом, как и всегда, символы ε, встречающиеся вдоль пути, ничего не до∧бавляют к w. Соответствующее рекурсивное определение δ имеет следующий вид.∧Базис.
δ (q, ε) = ECLOSE(q). Таким образом, если ε — метка пути, то мы можем совершать переходы лишь по дугам с меткой ε, начиная с состояния q; это дает нам в точности то же, что и ECLOSE(q).Индукция. Предположим, что w имеет вид xa, где a — последний символ w. Отметим, что a есть элемент Σ и, следовательно, не может быть ε, так как ε не принадлежит Σ.∧Мы вычисляем δ (q, w) следующим образом.∧1.Пусть {p1, p2, …, pk} есть δ (q, x), т.е. pi — это все те и только те состояния, в которые можно попасть из q по пути, отмеченному x. Этот путь может оканчиваться одним или несколькими ε-переходами, а также содержать и другие ε-переходы.2.ПустьkU δ (pi, a) есть множество {r1, r2, …, rm}, т.е. нужно совершить все переходы,i =1отмеченные символом a, из тех состояний, в которые мы можем попасть из q по пути, отмеченному x. Состояния ri — лишь некоторые из тех, в которые мы можемпопасть из q по пути, отмеченному w.
В остальные такие состояния можно попастьиз состояний ri посредством переходов с меткой ε, как описано ниже в (3).∧3.δ (q, w) =mUECLOSE(rj). На этом дополнительном шаге, где мы берем замыканиеj =1и добавляем все выходящие из q пути, отмеченные w, учитывается возможность существования дополнительных дуг, отмеченных ε, переход по которым может бытьсовершен после перехода по последнему ”непустому” символу a.∧Пример 2.20.
Вычислим δ (q0, 5.6) для ε-НКА на рис. 2.18. Для этого выполнимследующие шаги.•∧δ (q0, ε) = ECLOSE(q0) = {q0, q1}.∧• Вычисляем δ (q0, 5) следующим образом.2.5. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ Ñ ÝÏÑÈËÎÍ-ÏÅÐÅÕÎÄÀÌÈСтр. 93931.Находим переходы по символу 5 из состояний q0 и q1, полученных при вычислении∧δ (q0, ε): δ(q0, 5) U δ(q1, 5) = {q1, q4}.2.Находим ε -замыкание элементов, вычисленных на шаге (1).
Получаем:∧ECLOSE(q1) U ECLOSE(q4) = {q1} U {q4} = {q1, q4}, т.е. множество δ (q0, 5).Эта двушаговая схема применяется к следующим двум символам.∧• Вычисляем δ (q0, 5.).1.Сначала δ(q1, .) U δ(q4, .) = {q2} U {q3} = {q2, q3}.2.Затем δ (q0, 5.) = ECLOSE(q2) U ECLOSE(q3) = {q2} U {q3, q5} = {q2, q3, q5}.∧∧• Наконец, вычисляем δ (q0, 5.6).1.Сначала δ(q2, 6) U δ(q3, 6) U δ(q5, 6) = {q3} U {q3} U ∅ = {q3}.2.Затем δ (q0, 5.6) = ECLOSE(q3) = {q3, q5}.∧Теперь можно определить язык ε-НКА E = (Q, Σ, δ, q0, F) так, как и было задумано∧ранее: L(E) = {w | δ (q, w) I F ≠ ∅}. Таким образом, язык E — это множество цепочек w,которые переводят автомат из начального состояния хотя бы в одно из допускающих.∧Так, в примере 2.20 мы видели, что δ (q0, 5.6) содержит допускающее состояние q5, поэтому цепочка 5.6 принадлежит языку ε-НКА.2.5.5.
Óñòðàíåíèå ε-ïåðåõîäîâДля всякого ε-НКА E можно найти ДКА D, допускающий тот же язык, что и E. Поскольку состояния D являются подмножествами из состояний E, то используемая конструкция очень напоминает конструкцию подмножеств. Единственное отличие состоит втом, что нужно присоединить еще и ε-переходы E, применив механизм ε-замыкания.Пусть E = (QE, Σ, δE, qE, FE). Тогда эквивалентный ДКАD = (QD, Σ, δD, qD, FD)определяется следующим образом.1. QD есть множество подмножеств QE.
Точнее, как мы выясним, для D допустимымисостояниями являются только ε-замкнутые подмножества QE, т.е. такие множества S ⊆ QE, для которых S = ECLOSE(S). Иначе говоря, ε-замкнутые множествасостояний S — это такие множества, у которых всякий ε-переход из состояния,принадлежащего S, приводит снова в состояние из S. Заметим, что ∅ есть ε-замкнутое множество.2.94Стр. 94qD = ECLOSE(q0), т.е., замыкая множество, содержащее только начальное состояниеE, мы получаем начальное состояние D. Заметим, что это правило отличается от использованного ранее в конструкции подмножеств — там за начальное состояние поÃËÀÂÀ 2.
ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛстроенного автомата принималось множество, содержащее только начальное состояние данного НКА.3.FD — это такие множества состояний, которые содержат хотя бы одно допускающеесостояние автомата E. Таким образом, FD = {S | S принадлежит QD и S I FE ≠ ∅}.4.δD(S, a) для всех a из Σ и множеств S из QD вычисляется следующим образом:а) пусть S = {p1, p2, …, pk};б) вычислимkU δ (pi, a); пусть это будет множество {r1, r2, …, rm};i =1в) тогда δD(S, a) =mUECLOSE(rj).j =1Пример 2.21.
Удалим ε-переходы из ε-НКА (см. рис. 2.18), который далее называетсяE. По E мы строим ДКА D, изображенный на рис. 2.22. Для того чтобы избежать излишнего нагромождения, мы удалили на рис. 2.22 дьявольское состояние ∅ и все переходы внего. Поэтому, глядя на рис. 2.22, следует иметь в виду, что у каждого состояния естьеще дополнительные переходы в состояние ∅ по тем входным символам, для которыхпереход на рисунке отсутствует. Кроме того, у состояния ∅ есть переход в себя по любому входному символу.НачалоРис.
2.22. ДКА D, полученный устранением ε-переходов на рис. 2.18Поскольку начальное состояние E — это q0, начальным состоянием D являетсяECLOSE(q0), т.е. множество {q0, q1}. В первую очередь нужно найти состояния, в которые переходят q0 и q1 по различным символам из Σ; напомним, что это знаки плюс и минус, точка и цифры от 0 до 9. Как видно на рис. 2.18, по символам + и - q1 никуда не переходит, в то время как q0 переходит в q1.
Таким образом, чтобы вычислитьδD({q0, q1}, +), нужно взять ε-замыкание {q1}. Поскольку ε-переходов, выходящих из q1,нет, получаем, что δD({q0, q1}, +) = {q1}. Точно так же находится δD({q0, q1}, -) = {q1}.Эти два перехода изображены одной дугой на рис. 2.22.2.5. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ Ñ ÝÏÑÈËÎÍ-ÏÅÐÅÕÎÄÀÌÈСтр. 9595Теперь найдем δD({q0, q1}, .). Как видно на рис. 2.18, по точке q0 никуда не переходит, а q1 переходит в q2.
Поэтому нужно взять замыкание {q2}. Но состояние q2 являетсясобственным замыканием, так как ε-переходов из него нет.И, наконец, в качестве примера перехода из {q0, q1} по произвольной цифре найдемδD({q0, q1}, 0). По цифре q0 никуда не переходит, а q1 переходит сразу в q1 и q4. Так какни одно из этих состояний не имеет выходящих ε-переходов, делаем вывод, чтоδD({q0, q1}, 0) = {q1, q4}.
Последнее равенство справедливо для всех цифр.Итак, мы объяснили, как строятся дуги на рис. 2.22. Остальные переходы находятсяаналогично; проверка предоставляется читателю. Поскольку q5 есть единственное допускающее состояние E, допускающими состояниями D являются те его достижимые состояния, которые содержат q5. На рис. 2.22 эти два состояния, {q3, q5} и {q2, q3, q5}, отмечены двойными кружками. Теорема 2.22.
Язык L допускается некоторым ε-НКА тогда и только тогда, когда Lдопускается некоторым ДКА.Доказательство. (Достаточность) Доказательство в эту сторону просто. Допустим,L = L(D) для некоторого ДКА D. Преобразуем D в ε-НКА E, добавив переходыδ(q, ε) = ∅ для всех состояний q автомата D.
Чисто технически нужно также преобразовать переходы D по входным символам к виду НКА-переходов. Например, δD(q, a) = pнужно превратить в множество, содержащее только состояние p, т.е. δE(q, a) = {p}. Таким образом, E и D имеют одни и те же переходы, но при этом, совершенно очевидно, Eне содержит переходов по ε, выходящих из какого-либо состояния.(Необходимость) Пусть E = (QE, Σ, δE, qE, FE) — некоторый ε-НКА. Применим описанную выше модифицированную конструкцию подмножеств для построения ДКАD = (QD, Σ, δD, qD, FD).Нужно доказать, что L(D) = L(E). Для этого покажем, что расширенные функции пе∧реходов E и D совпадают.
Формально покажем индукцией по длине w, что δ E(q0, w) =∧δ D(q0, w).∧Базис. Если |w| = 0, то w = ε. По определению замыкания δ E(q0, ε) = ECLOSE(q0).Кроме того, по определению начального состояния D qD = ECLOSE(q0). Наконец, нам∧известно, что для любого ДКА δ (p, ε) = p, каково бы ни было состояние p. Поэтому, в∧∧∧частности, δ D(qD, ε) = ECLOSE(q0). Таким образом, доказано, что δ E(q0, ε) = δ D(qD, ε).Индукция. Предположим, что w = xa, где a — последний символ цепочки w, и что∧∧для x утверждение справедливо. Таким образом, δ E(q0, x) = δ D(qD, x). Пусть оба этимножества состояний представляют собой {p1, p2, …, pk}.∧∧По определению δ для ε-НКА находим δ E(q0, w) следующим образом.96Стр.
96ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ1.ПустьkU δ E(pi, a) есть {r1, r2, …, rm}.i =1∧2.Тогда δ E(q0, w) =mUECLOSE(rj).j =1Внимательно рассмотрев, как ДКА D строится посредством описанной выше моди∧фицированной конструкции подмножеств, мы видим, что δ D({p1, p2, …, pk}, a) построено с помощью описанных только что шагов (1) и (2). Таким образом, значение∧∧∧δ D(qD, w), т.е. δ D({p1, p2, …, pk}, a), совпадает с δ E(q0, w).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
