dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 18
Текст из файла (страница 18)
Оба эти факта следуют из диаграммыпереходов для автомата на рис. 2.9; как видно, по символу 0 есть переходы из q0 в q0 и q1,а по символу 1 — только в q0. Таким образом, получена вторая строка таблицы переходов ДКА на рис. 2.12.Одно из найденных множеств, {q0}, уже рассматривалось. Но второе, {q0, q1}, — новое, и переходы для него нужно найти: δD({q0, q1}, 0) = {q0, q1} и δD({q0, q1}, 1) = {q0, q2}.Проследить последние вычисления можно, например, так:δD({q0, q1}, 1) = δN(q0, 1) U δN(q1, 1) = {q0} U {q2}= {q0, q2}.Теперь получена пятая строка таблицы на рис. 2.12 и одно новое состояние {q0, q2}.Аналогичные вычисления показывают, чтоδD({q0, q2}, 0) = δN(q0, 0) U δN(q2, 0) = {q0, q1} U ∅ = {q0, q1},δD({q0, q2}, 1) = δN(q0, 1) U δN(q2, 1) = {q0} U ∅ = {q0}.Эти вычисления дают шестую строку таблицы на рис.
2.12, но при этом не получено ниодного нового множества состояний.Итак, конструкция подмножеств сошлась; известны все допустимые состояния и соответствующие им переходы. Полностью ДКА показан на рис. 2.14. Заметим, что онимеет лишь три состояния. Это число случайно оказалось равным числу состояний НКАна рис.
2.9, по которому строился этот ДКА. Но ДКА на рис. 2.14 имеет шесть переходов, а автомат на рис. 2.9 — лишь четыре. НачалоРис. 2.14. ДКА, построенный по НКА на рис. 2.92.3. ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 7979На последнем примере мы убедились, что конструкция подмножеств успешно работает. Теперь докажем это формально. По прочтении последовательности символов w построенный нами ДКА находится в состоянии, представляющем собой множество состояний НКА, в которые тот попадает, прочитав эту цепочку.
Но допускающие состоянияДКА — это состояния, которые содержат хотя бы одно допускающее состояние НКА, адопустимыми для НКА являются цепочки, приводящие его хотя бы в одно из допускающих состояний. Поэтому можно заключить, что ДКА и НКА допускают в точности однии те же цепочки. Следовательно, они допускают один и тот же язык.Теорема 2.11. Если ДКА D = (QD, Σ, δD, q0, FD) построен по НКА N = (QN, Σ, δN,q0, FN) посредством конструкции подмножеств, то L(D) = L(N).Доказательство. Вначале с помощью индукции по |w| покажем, что∧∧δ D({q0}, w) = δ N(q0, w).∧Заметим, что как для одной, так и для другой функции δ , значением является множе∧ство состояний из QN. При этом δ∧(являющегося булеаном QN), а δNDинтерпретирует его как состояние из QD— как подмножество QN.∧Базис.
Пусть |w| = 0, т.е. w = ε. Из базисных частей определений δ для ДКА и НКА∧∧имеем, что как δ D({q0}, ε), так и δ N(q0, ε) равны {q0}.Индукция. Пусть w имеет длину n + 1, и предположим, что утверждение справедливо для цепочки длины n. Разобьем w на w = xa, где a — последний символ цепочки w.∧∧Согласно гипотезе индукции δ D({q0}, x) = δ N(q0, x). Пусть оба эти множества состоянийN представляют собой {p1, p2, …, pk}.По индуктивной части определения для НКА∧δ N(q0, w) =kU δ N(pi, a).(2.2)i =1С другой стороны, конструкция подмножеств даетδD({p1, p2, …, p k}, a) =kU δ N(pi, a).(2.3)i =1Теперь, подставляя (2.3) в индуктивную часть определения для ДКА и используя тот∧факт, что δ D({q0}, x) = {p1, p2, …, pk}, получаем:∧∧δ D({q0}, w) = δD( δ D(q0, x), a)) = δD({p1, p2, …, pk}, a) =kU δ N(pi, a).(2.4)i =1∧∧Таким образом, из уравнений (2.2) и (2.4) видно, что δ D({q0}, w) = δ N(q0, w).
Далее, за∧∧мечая, что и D, и N допускают w тогда и только тогда, когда δ D({q0}, w) или δ N(q0, w)соответственно содержат некоторое состояние из FN, получаем полное доказательствотого, что L(D) = L(N). Теорема 2.12. Язык L допустим некоторым ДКА тогда и только тогда, когда он допускается некоторым НКА.80Стр. 80ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛДоказательство.
Достаточность следует из конструкции подмножеств и теоремы 2.11.(Необходимость) Доказательство этой части не представляет трудности; нам нужнолишь перейти от ДКА к идентичному НКА. Диаграмму переходов для некоторого ДКАможно рассматривать неформально как диаграмму переходов для некоторого НКА, причем последний имеет по любому входному символу лишь один переход. Точнее, пустьD = (Q, Σ, δD, q0, F) есть некоторый ДКА. Определим N = (Q, Σ, δN, q0, F) как эквивалентный ему НКА, где δN определена следующим правилом.• Если δD(q, a) = p, то δN(q, a) = {p}.∧Индукцией по |w| легко показать, что, если δ D(q, w) = p, то∧δ N(q0, w) = {p}.Доказательство предоставляется читателю.
Как следствие, D допускает w тогда и толькотогда, когда N допускает w, т.е. L(D) = L(N). 2.3.6. Ïëîõîé ñëó÷àé äëÿ êîíñòðóêöèè ïîäìíîæåñòâВ примере 2.10 мы обнаружили, что число состояний ДКА и число состояний НКАодинаково. Как мы уже говорили, ситуация, когда количества состояний НКА и построенного по нему ДКА примерно одинаковы, на практике встречается довольно часто. Однако при переходе от НКА к ДКА возможен и экспоненциальный рост числа состояний,т.е. все 2n состояний, которые могут быть построены по НКА, имеющему n состояний,оказываются достижимыми.
В следующем примере мы немного не дойдем до этого предела, но будет ясно, каким образом наименьший ДКА, построенный по НКА с n + 1 состояниями, может иметь 2n состояний.Пример 2.13. Рассмотрим НКА на рис. 2.15. L(N) есть множество всех цепочек из 0 и1, у которых n-м символом с конца является 1.
Интуиция подсказывает, что ДКА D, допускающий данный язык, должен помнить последние n прочитанных символов. Поскольку всего имеется 2n последовательностей, состоящих из последних n символов, топри числе состояний D меньше 2n нашлось бы состояние q, в которое D попадает по прочтении двух разных последовательностей, скажем, a1a2…an и b1b2…bn.НачалоРис.
2.15. Этот НКА не имеет эквивалентного ДКА, число состояний которого меньше 2nПоскольку последовательности различны, они должны различаться символом в некоторой позиции, например, ai ≠ bi. Предположим (с точностью до симметрии), что ai = 1и bi = 0. Если i = 1, то состояние q должно быть одновременно и допускающим, и недо2.3. ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 8181пускающим, поскольку последовательность a1a2…an допустима (n-й символ с конца есть1), а b1b2…bn — нет. Если же i > 1, то рассмотрим состояние p, в которое D попадает изсостояния q по прочтении цепочки из i – 1 нулей.
Тогда p вновь должно одновременно ибыть, и не быть допускающим, так как цепочка aiai+1…an00…0 допустима, аbibi+1…bn00…0 — нет.Теперь рассмотрим, как работает НКА N на рис. 2.15. Существует состояние q0, в котором этот НКА находится всегда, независимо от входных символов. Если следующийсимвол — 1, то N может “догадаться”, что эта 1 есть n-й символ с конца.
Поэтому одновременно с переходом в q0 НКА N переходит в состояние q1. Из состояния q1 по любомусимволу N переходит в состояние q2. Следующий символ переводит N в состояние q3 итак далее, пока n – 1 последующий символ не переведет N в допускающее состояние qn.Формальные утверждения о работе состояний N выглядят следующим образом.1.N находится в состоянии q0 по прочтении любой входной последовательности w.2.N находится в состоянии qi (i = 1, 2, …, n) по прочтении входной последовательности w тогда и только тогда, когда i-й символ с конца w есть 1, т.е.
w имеет видx1a1a2…ai-1, где aj — входные символы.“Ïðèíöèï ãîëóáÿòíè”В примере 2.13 мы использовали важный технический прием, применяемый в различных обоснованиях. Он называется принципом голубятни.4 Простыми словами, если у вас больше голубей, чем клеток для них, и каждый голубь залетает в одну из клеток, то хотя бы в одной клетке окажется больше одного голубя.
В нашем примере“голубями” являются последовательности из n элементов, а “клетками” — состояния.Поскольку состояний меньше, чем последовательностей, две различные последовательности должны вести в одно и то же состояние.Принцип голубятни может показаться очевидным, но в действительности он зависитот конечности числа клеток. Поэтому он применим к автоматам с конечным числомсостояний и неприменим к автоматам, число состояний которых бесконечно.Чтобы убедиться в том, что конечность числа клеток существенна, рассмотрим случай, когда есть бесконечное число клеток, соответствующих целым числам 1, 2, ….Пронумеруем голубей числами 0, 1, 2, …, т.е. так, чтобы их было на одного больше,чем клеток.
Тогда можно поместить голубя с номером i в (i + 1)-ю клетку для всехi ≥ 0. Тогда каждый из бесконечного числа голубей попадет в клетку, и никакие дваголубя не окажутся в одной клетке.Мы не доказываем эти утверждения формально. Скажем лишь, что доказательствопредставляет собой несложную индукцию по |w|, как в примере 2.9. Завершая доказа-82Стр.
82ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛтельство того, что данный автомат допускает именно те цепочки, у которых на n-й позиции с конца стоит 1, мы рассмотрим утверждение (2) при i = n. В нем говорится, что Nнаходится в состоянии qn тогда и только тогда, когда n-й символ с конца есть 1. Но qn является единственным допускающим состоянием, поэтому это условие также точно характеризует множество цепочек, допускаемых автоматом N.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
