dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 34
Текст из файла (страница 34)
То, что ни одна цепочка языка L1 не содержит символовc или d, несущественно, как и то, что ни одна цепочка языка L2 не содержит a.Аналогично, рассматривая дополнение языка L, который является подмножествоммножества Σ1* для некоторого алфавита Σ1, можно взять дополнение относительнонекоторого алфавита Σ2, включающего Σ1 (надмножества Σ1). В этом случае дополнением L будет Σ2* – L, т.е. дополнение языка L относительно алфавита Σ2 включает(среди прочих) все цепочки из Σ2*, которые содержат хотя бы один символ алфавитаΣ2, не принадлежащий Σ1. Если взять дополнение L относительно Σ1, то ни одна це__почка, содержащая символы из Σ2 – Σ1, не попадет в L .
Таким образом, чтобы избежать неточностей, нужно указывать алфавит, относительно которого берется дополнение. Часто, однако, бывает очевидно, какой алфавит подразумевается в конкретномслучае. Например, если язык L определен некоторым автоматом, то в описании этогоавтомата указывается и алфавит. Итак, во многих ситуациях можно говорить о “дополнении”, не указывая алфавит.4.2. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂСтр. 149149Оказывается, что класс регулярных языков замкнут относительно всех трех булевыхопераций, хотя, как будет видно, в доказательствах используются совершенно разныеподходы.Замкнутость относительно объединенияТеорема 4.4.
Если L и M — регулярные языки, то L U M также регулярен.Доказательство. Поскольку языки L и M регулярны, им соответствуют некоторыерегулярные выражения. Пусть L = L(R) и M = L(S). Тогда L U M = L(R + S) согласно определению операции + для регулярных выражений. Çàìêíóòîñòü îòíîñèòåëüíî ðåãóëÿðíûõ îïåðàöèéДоказательство замкнутости регулярных выражений относительно объединения былоисключительно легким, поскольку объединение является одной из трех операций, определяющих регулярные выражения. Идея доказательства теоремы 4.4 примениматакже к конкатенации и итерации.
Таким образом,• если L и M — регулярные языки, то язык LM регулярен;• если L — регулярный язык, то L* также регулярен.Замкнутость относительно дополненияТеорема для объединения языков легко доказывается с помощью регулярных выражений. Теперь рассмотрим дополнение. Знаете ли вы, как преобразовать регулярное выражение, чтобы оно определяло дополнение языка? Мы тоже не знаем. Однако это выполнимо, так как согласно теореме 4.5 можно начать с ДКА и построить ДКА, допускающий дополнение. Таким образом, начав с регулярного выражения для языка, можнонайти выражение для его дополнения следующим образом.1.Преобразовать регулярное выражение в ε-НКА.2.Преобразовать ε-НКА в ДКА с помощью конструкции подмножеств.3.Дополнить допускающие состояния этого ДКА.4.Преобразовать полученный ДКА для дополнения обратно в регулярное выражение,используя методы из разделов 3.2.1 или 3.2.2.__Теорема 4.5.
Если L — регулярный язык в алфавите Σ, то язык L = Σ* – L также регулярен.__Доказательство. Пусть L = L(A) для некоторого ДКА A = (Q, Σ, δ, q0, F). Тогда L = L(B),где B — это ДКА (Q, Σ, δ, q0, Q – F), т.е. автоматы A и B одинаковы, за исключением того, что допускающие состояния автомата A стали не допускающими в B, и наоборот. То∧гда w принадлежит L(B), если, и только если, δ (q0, w) принадлежит Q – F, т.е. w не принадлежит L(A). 150Стр.
150ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ∧Заметим, что для приведенного выше доказательства важно, чтобы δ (q0, w) всегдабыло некоторым состоянием. Это значит, что в автомате A все переходы определены.Если бы некоторые переходы отсутствовали, то определенные цепочки не вели бы ни вдопускающее, ни в недопускающее состояния автомата A, т.е. отсутствовали бы как вL(A), так и L(B).
К счастью, ДКА определен так, что в любом состоянии у него есть переход по каждому символу алфавита Σ, так что каждая цепочка приводит в состояние либоиз F, либо из Q – F.Пример 4.6. Пусть A — автомат, изображенный на рис. 2.14. Напомним, что этотДКА допускает те и только те цепочки символов 0 и 1, которые заканчиваются на 01. Втерминах регулярных выражений L(A) = (0 + 1)*01. Таким образом, дополнение к L(A)содержит все те цепочки из нулей и единиц, которые не заканчиваются на 01. На рис.
4.2представлен автомат для {0, 1}* – L(A). Он совпадает с автоматом на рис. 2.14, за исключением того, что допускающие состояния стали недопускающими, а два недопускающихсостояния стали допускающими. Пример 4.7. Используем теорему 4.5 для доказательства нерегулярности определенного языка. В примере 4.2 была доказана нерегулярность языка Leq, состоящего из цепочек с равными количествами символов 0 и 1. Это доказательство было непосредственным применением леммы о накачке.
Теперь рассмотрим язык M, состоящий из цепочек снеравными количествами нулей и единиц.НачалоРис. 4.2. ДКА, допускающий дополнение языка (0 + 1)*01В данном случае для доказательства нерегулярности языка M лемму о накачке применить трудно. Интуиция подсказывает, что если начать с некоторой цепочки w из M,разбить ее на w = xyz и “накачать” y, то может оказаться, что y — это цепочка вроде 01, вкоторой поровну символов 0 и 1. В этом случае не существует такого k, для которого цепочка xykz имела бы поровну нулей и единиц, поскольку xyz содержит неравные количества нулей и единиц, а при “накачивании” y эти количества изменяются одинаково. Следовательно, мы не можем использовать лемму о накачке для того, чтобы прийти к противоречию с предположением, что язык M регулярен.__Но все-таки язык M нерегулярен.
Объясняется это тем, что M = L eq . Поскольку дополнение к дополнению некоторого множества равно этому же множеству, то Leq = M .4.2. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂСтр. 151151Если M регулярен, то по теореме 4.5 язык Leq также регулярен. Но мы знаем, что Leq нерегулярен, и полученное противоречие доказывает нерегулярность языка M. Замкнутость относительно пересеченияРассмотрим пересечение двух регулярных языков.
Здесь почти нечего делать, посколькуоперации объединения, дополнения и пересечения не являются независимыми. Пересечениеязыков L и M выражается через объединение и дополнение следующим тождеством.L∩M = L ∪M(4.1)Вообще, пересечение двух множеств — это множество элементов, не принадлежащихдополнениям каждого из них.
Это замечание, записанное в виде равенства (4.1), представляет один из законов Де Моргана. Другой закон имеет аналогичный вид, только объединение и пересечение меняются местами, т.е. L ∪ M = L ∩ M .Вместе с тем, для пересечения двух регулярных языков можно построить ДКА непосредственно. Такая конструкция, в которой, по существу, параллельно работают дваДКА, весьма полезна сама по себе. Например, она использовалась для построения автомата (см. рис.
2.3), представляющего “произведение” действий двух участников — банкаи магазина. Конструкция произведения формально представлена в следующей теореме.Теорема 4.8. Если L и M — регулярные языки, то язык L I M также регулярен.Доказательство. Пусть L и M — языки автоматов AL = (QL, Σ, δL, qL, FL) и AM =(QM, Σ, δM, qM, FM). Заметим, что алфавиты автоматов считаются одинаковыми, т.е. Σесть объединение алфавитов языков L и M, если эти алфавиты различаются. В действительности конструкция произведения работает для НКА точно так же, как и для ДКА, нодля максимального упрощения предположим, что AL и AM — ДКА.Для L I M построим автомат A, моделирующий автоматы AL и AM одновременно.
Состояниями автомата A будут пары состояний, первое из которых принадлежит AL, а второе — AM. Чтобы построить переходы автомата A, предположим, что он находится в состоянии (p, q), где p — состояние автомата AL, а q — состояние AM. Нам известно, какведет себя автомат AL, получая на входе символ a. Пусть он переходит в состояние s.Также допустим, что автомат AM по входному символу a совершает переход в состояниеt.
Тогда следующим состоянием автомата A будет (s, t). Таким образом, автомат A моделирует работу автоматов AL и AM. Эта идея в общих чертах представлена на рис. 4.3.Остальные детали доказательства очень просты. Начальным состоянием автомата Aбудет пара начальных состояний автоматов AL и AM. Поскольку автомат A допускает тогда и только тогда, когда допускают оба автомата AL и AM, в качестве допускающих состояний автомата A выбираем все пары (p, q), где p — допускающее состояние автоматаAL, а q —AM. Формально автомат A определяется какA = (QL × QM, Σ, δ, (qL, qM), (FL × FM),где δ((p, q), a) = (δL(p, a), δM(q, a)).152Стр. 152ÃËÀÂÀ 4.
ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂВход аALИНачалоДопуститьAMРис. 4.3. Автомат, имитирующий два других автомата и допускающий тогда и только тогда,когда допускают оба автоматаЧтобы увидеть, почему L(A) = L(AL) I L(AM), сначала заметим, что индукцией по |w|∧∧∧легко доказать равенство δ ((qL, qM), w) = ( δ L(qL, w), δ M(qM, w)). Но A допускает w тогда∧и только тогда, когда δ ((qL, qM), w) является парой допускающих состояний, т.е.∧∧δ L(qL, w) должно принадлежать FL, а δ M(qM, w) — FM. Иными словами, цепочка w допускается автоматом A тогда и только тогда, когда ее допускают оба автомата AL и AM.Итак, A допускает пересечение языков L и M.
Пример 4.9. На рис. 4.4 представлены два ДКА. Автомат на рис. 4.4, а допускает всецепочки, имеющие 0, а автомат на рис. 4.4, б — все цепочки, имеющие 1. На рис. 4.4, впредставлен автомат — произведение двух данных автоматов. Его состояния помеченыкак пары состояний исходных автоматов.Легко доказать, что этот автомат допускает пересечение первых двух языков, т.е. тецепочки, которые содержат как 0, так и 1. Состояние pr представляет начальное условие,когда на вход автомата пока не поступили ни 0, ни 1. Состояние qr означает, что поступили только нули, а состояние ps — только единицы. Допускающее состояние qs представляет условие того, что на вход автомата поступили и нули, и единицы.
Замкнутость относительно разностиСуществует еще одна, четвертая, операция, часто применяемая к множествам и связанная с булевыми операциями, а именно, разность множеств. В терминах языков разностью L – M языков L и M называют множество цепочек, которые принадлежат L и непринадлежат M. Регулярные языки замкнуты относительно этой операции. Доказательство замкнутости относительно разности следует из доказанных выше теорем.4.2. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂСтр.
153153Началоа)Началоб)Началов)Рис. 4.4. Конструкция произведенияТеорема 4.10. Если L и M — регулярные языки, то язык L – M также регулярен.Доказательство. Заметим, что L – M = L I M . По теореме 4.5 регулярен язык M , апо теореме 4.8 — L I M . Следовательно, язык L – M регулярен. 4.2.2. ÎáðàùåíèåОбращением цепочки a1a2…an называется цепочка, записанная в обратном порядке,т.е. anan-1…a1. Обращение w обозначается wR. Таким образом, 0010R есть 0100, а εR = ε.Обращение языка L, обозначаемое LR, состоит из всех цепочек, обратных цепочкамязыка L. Например, если L = {001, 10, 111}, то LR = {100, 01, 111}.Обращение является еще одной операцией, сохраняющей регулярность языков, т.е.если язык L регулярен, то LR также регулярен.
Это легко доказать двумя способами, первый из которых основан на автоматах, а второй — на регулярных выражениях. Доказательство, основанное на автоматах, приводится неформально, так что читатель при желании может восполнить детали. Затем приводится формальное доказательство, использующее регулярные выражения.Если задан язык L, который есть L(A) для некоторого конечного автомата A, вероятно, с недетерминизмом и ε-переходами, то можно построить автомат для LR следующимобразом.1.Обратить все дуги на диаграмме переходов автомата A.2.Сделать начальное состояние автомата A единственным допускающим состояниемнового автомата.154Стр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
