dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 17
Текст из файла (страница 17)
Ðàñøèðåííàÿ ôóíêöèÿ ïåðåõîäîâ∧Для НКА, так же, как и для ДКА, нам потребуется расширить функцию δ до функцииδ , аргументами которой являются состояние q и цепочка входных символов w, а значением — множество состояний, в которые НКА попадает из состояния q, обработав це∧почку w. Эта идея проиллюстрирована на рис. 2.10. По сути, δ (q, w) есть столбец состояний, которые получаются при чтении цепочки w, при условии, что q — единственное∧состояние в первом столбце. Так, на рис.
2.10 видно, что δ (q0, 001) = {q0, q2}. Формаль∧но δ для НКА определяется следующим образом.∧Базис. δ (q, ε) = {q}, т.е., не прочитав никаких входных символов, НКА находитсятолько в том состоянии, в котором начинал.Индукция. Предположим, цепочка w имеет вид w = xa, где a — последний символ цепоч∧ки w, а x — ее оставшаяся часть. Кроме того, предположим, что δ (q, x) = {p1, p2, …, pk}.ПустьkU δ (pi, a) = {r1, r2, …, rm}.i =174Стр. 74ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ∧∧Тогда δ (q, w) = {r1, r2, …, rm}.
Говоря менее формально, для того, чтобы найти∧δ (q, w), нужно найти δ (q, x), а затем совершить из всех полученных состояний все переходы по символу a.∧Пример 2.8. Используем δ для описания того, как НКА на рис. 2.9 обрабатывает цепочку 00101.∧1.δ (q0, ε) = {q0}.2.δ (q0, 0) = δ (q0, 0) = {q0, q1}.3.δ (q0, 00) = δ (q0, 0) U δ (q1, 0) = {q0, q1} U ∅ = {q0, q1}.4.δ (q0, 001) = δ (q0, 1) U δ (q1, 1) = {q0} U {q2} = {q0, q2}.5.δ (q0, 0010) = δ (q0, 0) U δ (q2, 0) = {q0, q1} U ∅ = {q0, q1}.6.δ (q0, 00101) = δ (q0, 1) U δ (q1, 1) = {q0} U {q2} = {q0, q2}.∧∧∧∧∧Строка (1) повторяет основное правило.
Строку (2) получаем, применяя δ к единственному состоянию q0 из предыдущей строки. В результате получаем множество {q0, q1}.Строка (3) получается объединением двух состояний предыдущего множества и применением к каждому из них δ с входным символом 0, т.е. δ(q0, 0) = {q0, q1}, и δ(q1, 0) = ∅.Для того чтобы получить строку (4), берется объединение δ(q0, 1) = {q0} и δ(q1, 1) = {q2}.Строки (5) и (6) получены так же, как строки (3) и (4). 2.3.4. ßçûê ÍÊÀПо нашему описанию НКА допускает цепочку w, если в процессе чтения этой цепочки символов можно выбрать хотя бы одну последовательность переходов в следующиесостояния так, чтобы прийти из начального состояния в одно из допускающих.
Тот факт,что при другом выборе последовательности переходов по символам цепочки w мы можем попасть в недопускающее состояние или вообще не попасть ни в какое (т.е. последовательность состояний “умирает”), отнюдь не означает, что w не является допустимойдля НКА в целом. Формально, если A = (Q, Σ, δ, q0, F) — некоторый НКА, то∧L(A) = {w | δ (q0, w) I F = ∅}.∧Таким образом, L(A) есть множество цепочек w из Σ*, для которых среди состоянийδ (q0, w) есть хотя бы одно допускающее.Пример 2.9. В качестве примера докажем формально, что НКА на рис.
2.9 допускаетязык L = {w | w оканчивается на 01}. Доказательство представляет собой совместную индукцию следующих трех утверждений, характеризующих три состояния.∧1.δ (q0, w) содержит q0 для всякой цепочки w.2.δ (q0, w) содержит q1 тогда и только тогда, когда w оканчивается на 0.3.δ (q0, w) содержит q2 тогда и только тогда, когда w оканчивается на 01.∧∧2.3. ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр.
7575Чтобы доказать эти утверждения, нужно рассмотреть, каким образом A может попасть в каждое из этих состояний, т.е. каким был последний входной символ, и в какомсостоянии находился A непосредственно перед тем, как прочитал этот символ.Поскольку язык этого автомата есть множество цепочек w, для которых∧δ (q0, w) содержит q2 (так как q2 — единственное допускающее состояние), то доказательство этих трех утверждений, в частности, доказательство 3, гарантирует, что языкданного НКА есть множество цепочек, оканчивающихся на 01. Доказательство этойтеоремы представляет собой индукцию по |w|, длине цепочки w, начиная с нуля.∧Базис. Если |w| = 0, то w = ε. В утверждении 1 говорится, что δ (q0, ε) содержит q0.
Но∧это действительно так в силу базисной части определения δ . Рассмотрим теперь утверждение 2. Мы знаем, что ε не заканчивается на 0, и, кроме того, опять же в силу базисной∧части определения δ (q0, ε) не содержит q1. Таким образом, гипотезы утверждения 2 типа “тогда и только тогда” в обе стороны ложны. Поэтому само утверждение является истинным в обе стороны. Доказательство утверждения 3, по сути, повторяет доказательство утверждения 2.Индукция. Допустим, что w = xa, где a есть символ 0 или 1. Можно предположить,что утверждения 1–3 выполняются для x.
Нужно доказать их для w, предположив, что|w| = n + 1, а |x| = n. Предполагая, что гипотеза индукции верна для n, докажем ее дляn + 1.∧Нам известно, что δ (q0, x) содержит q0. Поскольку по обоим входным символам 0 и1.∧1 существуют переходы из q0 в себя, то δ (q0, w) также содержит q0. Таким образом,утверждение 1 доказано для w.(Достаточность) Предположим, что w оканчивается на 0, т.е. a = 0. Применяя ут-2.∧верждение 1 к x, получаем, что δ (q0, x) содержит q0. Поскольку по символу 0 суще∧ствует переход из q0 в q1, заключаем, что δ (q0, w) содержит q1.∧(Необходимость) Допустим, что δ (q0, w) содержит q1. По диаграмме на рис. 2.9видно, что единственная возможность попасть в состояние q1 реализуется, когда wимеет вид x0. Это доказывает необходимость в утверждении 2.3.
(Достаточность) Предположим, что w оканчивается на 01. Тогда если w = xa, томы знаем, что a = 1, а x оканчивается на 0. Применив утверждение 2 к x, получим,∧что δ (q0, x) содержит q1. Поскольку по символу 1 существует переход из q1 в q2,∧приходим к выводу, что δ (q0, w) содержит q2.∧(Необходимость) Допустим, что δ (q0, w) содержит q2. По диаграмме на рис. 2.9видно, что в состояние q2 можно попасть тогда и только тогда, когда w имеет вид x176Стр. 76ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ∧и δ (q0, x) содержит q1.
Применяя утверждение 2 к x, получим, что x оканчивается на0. Таким образом, w оканчивается на 01, и утверждение 3 доказано.2.3.5. Ýêâèâàëåíòíîñòü äåòåðìèíèðîâàííûõ è íåäåòåðìèíèðîâàííûõêîíå÷íûõ àâòîìàòîâДля многих языков, в частности, для языка цепочек, оканчивающихся на 01(пример 2.6), построить соответствующий НКА гораздо легче, чем ДКА. Несмотря наэто, всякий язык, который описывается некоторым НКА, можно также описать и некоторым ДКА. Кроме того, этот ДКА имеет, как правило, примерно столько же состояний,сколько и НКА, хотя часто содержит больше переходов. Однако в худшем случае наименьший ДКА может содержать 2n состояний, в то время как НКА для того же самогоязыка имеет всего n состояний.В доказательстве того, что ДКА обладают всеми возможностями НКА, используетсяодна важная конструкция, называемая конструкцией подмножеств, поскольку включаетпостроение всех подмножеств множества состояний НКА.
Вообще, в доказательствахутверждений об автоматах часто по одному автомату строится другой. Для нас конструкция подмножеств важна в качестве примера того, как один автомат описывается втерминах состояний и переходов другого автомата без знания специфики последнего.Построение подмножеств начинается, исходя из НКА N = (QN, Σ, δN, q0, FN). Цельюявляется описание ДКА D = (QD, Σ, δD, {q0}, FD), у которого L(N) = L(D). Отметим, чтовходные алфавиты этих двух автоматов совпадают, а начальное состояние D есть множество, содержащее только начальное состояние N.
Остальные компоненты D строятсяследующим образом.• QD есть множество всех подмножеств QN, или булеан множества QN. Отметим,что если QN содержит n состояний, то QD будет содержать уже 2n состояний. Однако часто не все они достижимы из начального состояния автомата D. Такие недостижимые состояния можно “отбросить”, поэтому фактически число состоянийD может быть гораздо меньше, чем 2n.• FD есть множество подмножеств S множества QN, для которых S I FN ≠ ∅, т.е. FDсостоит из всех множеств состояний N, содержащих хотя бы одно допускающеесостояние N.• Для каждого множества S ⊆ QN и каждого входного символа a из ΣδD(S, a) =UδN(p, a).p из SТаким образом, для того, чтобы найти δD(S, a), мы рассматриваем все состояния p из S, ищем те состояния N, в которые можно попасть из состояния p по2.3.
ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 7777символу a, а затем берем объединение множеств найденных состояний по всемсостояниям p.Пример 2.10. Пусть N — автомат на рис. 2.9, допускающий цепочки, которые оканчиваются на 01. Поскольку множество состояний N есть {q0, q1, q2}, то конструкция подмножеств дает ДКА с 23 = 8 состояниями, отвечающими всем подмножествам, составленным из этих трех состояний.
На рис. 2.12 приведена таблица переходов для полученных восьми состояний. Объясним вкратце, как были получены элементы этой таблицы.01∅∅{q0, q1}{q0}{q1}∅{q2}*{q2}∅∅{q0, q1}{q0, q1}{q0, q2}*{q0, q2}{q0, q1}{q0}*{q1, q2}∅{q2}{q0, q1}{q0, q2}∅→ {q0}*{q0, q1, q2}Рис. 2.12. Полная конструкция подмножеств для автомата на рис. 2.9Заметим, что данная таблица, элементами которой являются множества, соответствует детерминированному конечному автомату, поскольку состояния построенного ДКАсами являются множествами. Для ясности можно переобозначить состояния.
Например, ∅ обозначить как A, {q0} — как B и т.д. Таблица переходов для ДКА на рис. 2.13определяет в точности тот же автомат, что и на рис. 2.12, и из ее вида понятно, что элементами таблицы являются одиночные состояния ДКА.01AAA→BEBCAD*DAAEEF*FEB*GAD*HEFРис. 2.13. Переименование состояний на рис. 2.1278Стр. 78ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛНачиная в состоянии B, из всех восьми состояний мы можем попасть только в состояния B, E и F.
Остальные пять состояний из начального недостижимы, и поэтому ихможно исключить из таблицы. Часто можно избежать построения элементов таблицыпереходов для всех подмножеств, что требует экспоненциального времени. Для этоговыполняется следующее “ленивое вычисление” подмножеств.Базис. Мы точно знаем, что одноэлементное множество, состоящее из начальногосостояния N, является достижимым.Индукция.
Предположим, мы установили, что множество состояний S является достижимым. Тогда для каждого входного символа a нужно найти множество состоянийδD(S, a). Найденные таким образом множества состояний также будут достижимы.Элементарный пример: нам известно, что {q0} есть одно из состояний ДКА D. Находим, что δD({q0}, 0) = {q0, q1} и δD({q0}, 1) = {q0}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
