Свойства регулярных языков (1134638), страница 2
Текст из файла (страница 2)
Цепочка xz содержит n единиц, так как все единицы цепочки w попадают в z. Нов xz нулей меньше n, так как потеряны все нули из y. Поскольку y ≠ ε, то вместе x и z содержат не более n – 1 нулей. Таким образом, предположив, что язык Leq регулярен, приходим к ошибочному выводу, что цепочка xz принадлежит Leq. Следовательно, методомот противного доказано, что язык Leq нерегулярен. Пример 4.3. Докажем нерегулярность языка Lpr, образованного всеми цепочками изединиц, длины которых — простые числа. Предположим, что язык Lpr регулярен.
Тогдадолжна существовать константа n, удовлетворяющая условиям леммы о накачке. Рассмотрим некоторое простое число p ≥ n + 2. Такое p должно существовать, посколькумножество простых чисел бесконечно. Пусть w = 1p.Согласно лемме о накачке можно разбить цепочку w = xyz так, что y ≠ ε и |xy| ≤ n.Пусть |y| = m. Тогда |xz| = p – m. Рассмотрим цепочку xyp–mz, которая по лемме о накачкедолжна принадлежать языку Lpr, если он действительно регулярен. Однако|xyp–mz| = |xz| + (p – m)|y| = p – m + (p – m)m = (m + 1)(p – m).2146Заметим, что можно выиграть и при k = 2 или любом другом значении k, кроме k = 1.ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂПохоже, что число |xyp–mz| не простое, так как имеет два множителя m + 1 и p – m. Однако нужно еще убедиться, что ни один из этих множителей не равен 1, потому что тогдачисло (m + 1)(p – m) будет простым.
Из неравенства y ≠ ε следует m ≥ 1 и m + 1 > 1. Кроме того, m = |y| ≤ |xy| ≤ n, а p ≥ n + 2, поэтому p – m ≥ 2.Мы начали с предположения, что предлагаемый язык регулярен, и пришли к противоречию, доказав, что существует некоторая цепочка, которая не принадлежит этомуязыку, тогда как по лемме о накачке она должна ему принадлежать. Таким образом, языкLpr нерегулярен. 4.1.3. Óïðàæíåíèÿ ê ðàçäåëó 4.14.1.1.Докажите нерегулярность следующих языков:а) {0n1n | n ≥ 1}.
Это язык L01, который рассматривался в начале раздела. Емупринадлежат все цепочки, состоящие из нулей, за которыми следует такое жеколичество единиц. Здесь для доказательства примените лемму о накачке;б) множество цепочек, состоящих из “сбалансированных” скобок “(” и “)”, которые встречаются в правильно построенном арифметическом выражении;в) (∗) {0n10n | n ≥ 1};г) {0n1m2n | n и m — произвольные целые числа};д) {0n1m | n ≤ m};е) {0n12n | n ≥ 1}.4.1.2.(!) Докажите нерегулярность следующих языков:а) (∗) {0n | n — полный квадрат};б) {0n | n — полный куб};в) {0n | n — степень числа 2};г) множество цепочек из нулей и единиц, длины которых — полные квадраты;д) множество цепочек из нулей и единиц вида ww, где некоторая цепочка w повторяется дважды;е) множество цепочек из нулей и единиц вида wwR, где за цепочкой следует цепочка, обратная к ней (формальное определение цепочки, обратной к данной,см.
в разделе 4.2.2);ж) множество цепочек из нулей и единиц вида w w , где цепочка w образованаиз w путем замены всех нулей единицами и наоборот. Например, 011 = 100,так что цепочка 011100 принадлежит данному языку;з) множество цепочек из нулей и единиц вида w1n, где w — цепочка из нулей иединиц длиной n.4.1. ÄÎÊÀÇÀÒÅËÜÑÒÂÎ ÍÅÐÅÃÓËßÐÍÎÑÒÈ ßÇÛÊÎÂ1474.1.3.(!!) Докажите нерегулярность следующих языков:а) множество всех цепочек из нулей и единиц, которые начинаются с единицыи удовлетворяют следующему условию: если интерпретировать такую цепочку как целое число, то это число простое;3б) множество цепочек вида 0i1j, для которых наибольший общий делитель чисел i и j равен 1.4.1.4.(!) При попытке применения леммы о накачке к регулярным языкам “противниквыигрывает”, и закончить доказательство не удается. Определите, что именнопроисходит не так, как нужно, если в качестве L выбрать следующий язык:а) (∗) пустое множество;б) (∗) {00, 11};в) (∗) (00 + 11)*;г) 01*0*1.4.2.
Ñâîéñòâà çàìêíóòîñòè ðåãóëÿðíûõ ÿçûêîâВ этом разделе доказано несколько теорем вида “если определенные языки регулярны, а язык L построен из них с помощью определенных операций (например, L есть объединение двух регулярных языков), то язык L также регулярен”. Эти теоремы часто называют свойствами замкнутости регулярных языков, так как в них утверждается, чтокласс регулярных языков замкнут относительно определенных операций. Свойства замкнутости выражают идею того, что если один или несколько языков регулярны, то языки,определенным образом связанные с ним (с ними), также регулярны. Кроме того, данныесвойства служат интересной иллюстрацией того, как эквивалентные представления регулярных языков (автоматы и регулярные выражения) подкрепляют друг друга в нашемпонимании этого класса языков, так как часто один способ представления намного лучше других подходит для доказательства некоторого свойства замкнутости.Основные свойства замкнутости регулярных языков выражаются в том, что эти языкизамкнуты относительно следующих операций.1.Объединение.2.Пересечение.3.Дополнение.4.Разность.5.Обращение.3148Иными словами, это двоичные записи простых чисел.
— Прим. ред.ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ6.Итерация (звездочка).7.Конкатенация.8.Гомоморфизм (подстановка цепочек вместо символов языка).9.Обратный гомоморфизм.4.2.1. Çàìêíóòîñòü ðåãóëÿðíûõ ÿçûêîâ îòíîñèòåëüíîáóëåâûõ îïåðàöèéСначала рассмотрим замкнутость для трех булевых операций: объединение, пересечение и дополнение.1.Пусть L и M — языки в алфавите Σ.
Тогда язык L U M содержит все цепочки, которые принадлежат хотя бы одному из языков L или M.2.Пусть L и M — языки в алфавите Σ. Тогда язык L I M содержит все цепочки, принадлежащие обоим языкам L и M.3.Пусть L — некоторый язык в алфавите Σ. Тогда язык L , дополнение L, — это множество тех цепочек в алфавите Σ*, которые не принадлежат L.×òî äåëàòü, åñëè ÿçûêè èìåþò ðàçíûå àëôàâèòû?При объединении или пересечении двух языков L и M может оказаться, что они определены в разных алфавитах. Например, возможен случай, когда L1 ⊆ {a, b}, а L2 ⊆{b, c, d}.
Однако, если язык L состоит из цепочек символов алфавита Σ, то L можнотакже рассматривать как язык в любом конечном алфавите, включающем Σ(надмножестве Σ). Например, можно представить указанные выше языки L1 и L2 какязыки в алфавите {a, b, c, d}. То, что ни одна цепочка языка 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. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ149Оказывается, что класс регулярных языков замкнут относительно всех трех булевыхопераций, хотя, как будет видно, в доказательствах используются совершенно разныеподходы.Замкнутость относительно объединенияТеорема 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ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ∧Заметим, что для приведенного выше доказательства важно, чтобы δ (q0, w) всегдабыло некоторым состоянием.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
