dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 36
Текст из файла (страница 36)
Но если ни одно из условий 1–4 не выполняется, то цепочка wимеет вид baba…ba. Чтобы понять, почему это происходит, предположим, что ни одноиз этих условий не выполняется. Тогда невыполнение условия 1 означает, что w должнаначинаться символом b, а невыполнение 2 — что она должна заканчиваться символом a.Невыполнение условий 3 и 4 говорит, что символы a и b должны чередоваться. Следовательно, логическое ИЛИ условий 1–4 эквивалентно утверждению “цепочка w имеет вид,отличный от baba…ba”.
Но выше было доказано, что из логического ИЛИ условий 1–4следует, что h(w) не принадлежит L. Это утверждение противоположно тому, что нужнодоказать, а именно, что “если h(w) принадлежит L, то цепочка w имеет вид baba…ba”. Далее докажем, что обратный гомоморфизм регулярного языка также регулярен, ипокажем, как эту теорему можно использовать.Теорема 4.16. Если h — гомоморфизм из алфавита Σ в алфавит T, L — регулярныйязык над T, то язык h–1(L) также регулярен.Доказательство. Начнем с ДКА A для языка L. По A и h строится ДКА для h-1(L) спомощью схемы, представленной на рис.
4.6. Этот ДКА использует состояния автоматаA, но переводит входной символ в соответствии с h перед тем, как решить, в какое состояние перейти.ВходНачалоВход( ) дляДопустить/отвергнутьРис. 4.6. ДКА для h–1(L) применяет гомоморфизм h ко входным символам,а потом имитирует ДКА для LФормально, пусть L — это L(A), где ДКА A = (Q, T, δ, q0, F). Определим ДКАB = (Q, Σ, γ, q0, F),∧функция переходов γ которого строится по правилу γ(q, a) = δ (q, h(a)). Таким образом,переход автомата B по входному символу a является результатом последовательностипереходов, совершаемых автоматом A при получении цепочки символов h(a). Напомним,4.2.
ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂСтр. 159159что, хотя h(a) может равняться ε, состоять из одного или нескольких символов, функция∧δ определена так, чтобы справиться со всеми этими случаями.∧)С помощью индукции по |w| легко показать, что γ (q0, w) = δ (q0, h(w)). Посколькудопускающие состояния автоматов A и B совпадают, то B допускает цепочку w тогда итолько тогда, когда A допускает цепочку h(w). Иными словами, B допускает только тецепочки, которые принадлежат языку h–1(L).
Пример 4.17. В этом примере обратный гомоморфизм и некоторые другие свойствазамкнутости регулярных множеств используются для доказательства одного необычногосвойства конечных автоматов. Предположим, что, допуская входную цепочку, некоторыйавтомат должен побывать в каждом состоянии хотя бы по одному разу. Точнее, допустим,что A = (Q, Σ, δ, q0, F) — ДКА, и нас интересует язык L, состоящий из всех цепочек w в ал∧фавите Σ*, для которых δ (q0, w) принадлежит F, и для каждого состояния q из Q существу∧ет некоторый префикс xq цепочки w, для которого δ (q0, xq) = q. Будет ли язык L регулярным? Докажем, что такой язык регулярен, хотя доказательство довольно сложное.Начнем с языка M = L(A), т.е. множества цепочек, допускаемых автоматом A обычнымпутем, независимо от того, в какие состояния он переходит, обрабатывая входную цепочку.Заметим, что L ⊆ M, так как определение языка L накладывает дополнительные ограничения на цепочки из L(A).
Доказательство регулярности языка L начинается с использованияобратного гомоморфизма для вставки состояний автомата A во входные символы. Точнее,определим новый алфавит T как состоящий из символов, которые можно представить в виде троек [paq], где p и q — состояния из Q, a — символ из Σ, и δ(p, a) = q.Таким образом, символы алфавита T представляют переходы автомата A. Важно понимать, что запись [paq] представляет собой единый символ, а не конкатенацию трехсимволов.
Можно обозначить этот символ одной буквой, но при этом трудно описать егосвязь с p, q и a.Теперь определим гомоморфизм h([paq]) = a для всех p, a и q. Это значит, что гомоморфизм h удаляет из каждого символа алфавита T компоненты, представляющие состояния, и оставляет только символ из Σ. Первый шаг доказательства регулярности языкаL состоит в построении языка L1 = h–1(M). Поскольку язык M регулярен, то согласно теореме 4.16 язык L1 также регулярен. Цепочками языка L1 будут цепочки из M, к каждомусимволу которых присоединяется пара состояний, представляющая некоторый переходавтомата.В качестве простого примера рассмотрим автомат с двумя состояниями, представленный на рис.
4.4, а. Алфавит Σ = {0, 1}, а алфавит T состоит из четырех символов[p0q], [q0q], [p1p] и [q1q]. Например, поскольку по символу 0 есть переход из p в q, то[p0q] — один из символов алфавита T. Так как цепочка 101 допускается этим автоматом,применив к ней обратный гомоморфизм h–1, получим 23 = 8 цепочек, две из которых, например, равны [p1p][p0q][q1q] и [q1q][q0q][p1p].160Стр. 160ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂТеперь по языку L1 построим язык L с помощью ряда операций, сохраняющих регулярность языков.
Наша первая цель — исключить все те цепочки языка L1, в которых состояния указаны неправильно. Поскольку каждый символ вида [paq] означает, что автомат был в состоянии p, прочитал a и затем перешел в состояние q, последовательностьтаких символов, представляющая допускающее вычисление в автомате A, должна удовлетворять следующим трем условиям.1.Первым состоянием в первом символе должно быть q0 — начальное состояние A.2.Каждый переход автомата должен начинаться там, где закончился предыдущий, т.е.
первое состояние в символе должно равняться второму состоянию в предыдущем символе.3.Второе состояние в последнем символе должно принадлежать F. Если выполняютсяпервые два условия, то и это условие будет выполнено, поскольку каждая цепочкаязыка L1 образована из цепочки, допускаемой автоматом A.Язык автомата AОбратный гомоморфизмЦепочки языка M, в которые вставлены компоненты состоянийПересечение с регулярным языкомДобавить условие, что первым является начальное состояниеРазница с регулярным языкомДобавить условие, что смежные состояния должны совпадатьРазница с регулярными языкамиДобавить условие, что на пути встречаются все состоянияГомоморфизмУдалить компоненты состояний, оставляя только символыРис.
4.7. Построение языка L по языку M с помощью операций,сохраняющих регулярность языков4.2. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂСтр. 161161План построения языка L представлен на рис. 4.7.Условие 1 обеспечивается пересечением языка L1 со множеством цепочек, которые начинаются символом вида [q0aq] для некоторого символа a и состояния q. Пусть E1 — выражение [q0a1q1] + [q0a2q2] + …, где aiqi — все пары из Σ × Q, для которых δ(q0, ai) = qi.Пусть L2 = L1 I L(E1T*). Регулярное выражение E1T* обозначает все цепочки из T*, которыеначинаются стартовым состоянием (здесь T можно рассматривать как сумму всех его символов).
Поэтому язык L2 состоит из всех цепочек, полученных в результате применения обратного гомоморфизма h–1 к языку M, у которых первым компонентом в первом символеявляется начальное состояние, т.е. язык L2 удовлетворяет условию 1.Чтобы обеспечить выполнение условия 2, проще всего вычесть из L2 (используя операцию разности множеств) все цепочки, нарушающие это условие. Пусть E2 — регулярное выражение, состоящее из суммы (объединения) конкатенаций всех пар символов, которые друг другу не подходят. Это все пары вида [paq][rbs], где q ≠ r.
Тогда регулярноевыражение T*E2T* обозначает все цепочки, не удовлетворяющие условию 2.Теперь можно определить L3 = L2 – L(T*E2T*). Цепочки языка L3 удовлетворяют условию 1, поскольку цепочки языка L2 начинаются стартовым состоянием. Они также удовлетворяют условию 2, так как в результате вычитания L(T*E2T*) будут удалены все цепочки, для которых это условие не выполняется. Наконец, они удовлетворяют условию 3(последнее состояние является допускающим), поскольку доказательство было начато сцепочек языка M, допускаемых автоматом A.
В результате L3 состоит из цепочек языка Mс состояниями допускающего вычисления такой цепочки, вставленными в каждый символ. Заметим, что язык L3 регулярен, так как он построен из регулярного языка M с помощью операций обратного гомоморфизма, пересечения и разности множеств, сохраняющих регулярность.Напомним, что наша цель состоит в том, чтобы допустить только те цепочки из M,при обработке которых автомат проходит через каждое состояние. Выполнение этого условия можно обеспечить с помощью операции разности множеств. Пусть для каждогосостояния q регулярное выражение Eq представляет собой сумму всех символов алфавитаT, в которые не входит состояние q (q не стоит ни на первой, ни на последней позиции).В результате вычитания языка L(Eq*) из L3 получим цепочки, представляющие допускающее вычисление автомата A и проходящие через состояние q, по крайней мере, одинраз.
Если вычесть из L3 языки L(Eq*) для всех q из Q, то получим допускающие вычисления автомата A, проходящие через все состояния. Обозначим этот язык L4. По теореме 4.10 язык L4 также регулярен.Последний шаг состоит в построении языка L из L4 с помощью исключения компонентов состояний, т.е. L = h(L4). Теперь L является множеством цепочек в алфавите Σ*,допускаемых автоматом A, причем при их обработке автомат проходит через каждое состояние, по крайней мере, один раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
