Свойства регулярных языков (1134638), страница 3
Текст из файла (страница 3)
Это значит, что в автомате 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. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ151Если 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ÃËÀÂÀ 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. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ153Началоа)Началоб)Началов)Рис. 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ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ3.Создать новое начальное состояние p0 с ε-переходами во все допускающие состояния автомата A.В результате получим автомат, имитирующий автомат A “в обратном порядке” и, следовательно, допускающий цепочку w тогда и только тогда, кода A допускает wR.Теперь докажем теорему для обращения формально.Теорема 4.11.
Если язык L регулярен, то язык LR также регулярен.Доказательство. Предположим, что язык L определяется регулярным выражением E.Доказательство проводится структурной индукцией по длине выражения E. Покажем,что существует еще одно регулярное выражение ER, для которого L(ER) = (L(E))R, т.е.язык выражения ER является обращением языка выражения E.Базис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
