Свойства регулярных языков (1134638), страница 5
Текст из файла (страница 5)
Далее докажем, что обратный гомоморфизм регулярного языка также регулярен, ипокажем, как эту теорему можно использовать.Теорема 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. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ159что, хотя 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ÃËÀÂÀ 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. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ161План построения языка 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, причем при их обработке автомат проходит через каждое состояние, по крайней мере, один раз.
Поскольку регулярные языки замкнуты относительно гомоморфизмов, делаем вывод, что язык L регулярен. 162ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ4.2.5. Óïðàæíåíèÿ ê ðàçäåëó 4.24.2.1.Пусть h — гомоморфизм из алфавита {0, 1, 2} в алфавит {a, b}, определенныйкак h(0) = a, h(1) = ab и h(2) = ba:а) (∗) найдите h(0120);б) найдите h(21120);в) (∗) найдите h(L) для L = L(01*2);г) найдите h(L) для L = L(0 + 12);д) (∗) найдите h–1(L) для L = {ababa}, т.е. языка, состоящего из однойединственной цепочки ababa;е) (!) найдите h–1(L) для L = L(a(ba)*).4.2.2. (∗!) Если L — язык, а — символ, то L/a, частное L и a, — это множество цепочекw, для которых wa принадлежит L. Например, если L = {a, aab, baa}, то L/a ={ε, ba}.
Докажите, что из регулярности L следует регулярность L/a. Указание.Начните с ДКА для L и рассмотрите множество допускающих состояний.4.2.3. (!) Если L — язык, а — символ, то a\L — это множество цепочек w, для которыхaw принадлежит L. Например, если L = {a, aab, baa}, то a\L = {ε, ab}. Докажите,что из регулярности L следует регулярность a\L. Указание. Вспомните, что регулярные языки замкнуты относительно обращения и операции деления из упражнения 4.2.2.4.2.4. (!) Какие из следующих тождеств истинны?а) (L/a)a = L (в левой части представлена конкатенация языков L/a и {a}).б) a(a\L) = L (снова представлена конкатенация с языком {a}, но на этот разслева).в) (La)/a = L.г) a\(aL) = L.4.2.5. Операция из упражнения 4.2.3 иногда рассматривается как “производная”, а выраdL.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
