Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 33
Текст из файла (страница 33)
Предположим, что язык Ер, ре~улярен. Тогда должна существовать константа л, удовлетворяющая условиям леммы о накачке. Рассмотрим некоторое простое число р > л ь 2. Такое р должно существовать, поскольку множество простых чисел бесконечно. Пусть зк =- !в. Согласно лемме о накачке можно разбить цепочку н =ху так, что уп е и !ху~ <и. Пусть 1у( = т. Тогда (хх~ = р — т. Рассмотрим цепочку ху' ", которая по лемме о накачке должна принадлежать языку Ерп если он действительно регулярен. Однако (хув х( = !хг! .ь 1р — т)'у! = р — т .ь 1р — т)т = (т ч 1)1р — т). ' Заметим, что можно выиграть н ори к.= 2 или любом другом значении ~„кроме к = 1. ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 14б Похоже, что число (»у' я! не простое, так как имеет два множителя т+ ! и р — т. Од!цко нужно еще убедиться, что ни один из этих множителей не равен 1, потому что тогда ввело (т+ 1)(р — т) будет простым.
Из неравенства у и е следует т > 1 и т + 1 > 1. Кроне того, и = (у! < (яу~ < и, а р > и + 2, поэтому р — т > 2. Мы начали с предположения, что предлагаемый язык регулярен, и пришли к противоречию, доказав, что существует некоторая цепочка, которая не принадлежит этому языку„тогда как по лемме о накачке она лолжна ему принадлежать. Таким образом, язык 1, аерегулярен. П 4.1,3.
Упражнения к разделу 4.1 4.1.1. Докажите нерегулярность следующих языков; а) (О"1" ! п> 1). Это язык Дщ который рассматривался в начале раздела. Ему принадлежат все цепочки, состоящие из нулей, за которыми следует такое же количество единиц. Здесь для доказательства примените лемму о накачке; б) множество цепочек, состоящих из "сбалансированных" скобок "(" и ")", которые встречаются в правильно построенном арифметическом выражении; в) (в) (О"10" )п > 1); г) (О" 1 2" ! п и т — произвольные целые числа); д) (О"1 )пйт); е) (О" 1 " ! п Е 1) . 4.1.2. (!) Докажите нерегулярность следующих языков: а) (» ) (О" ! п — полный квадрат); б) (О" )и — полный куб); в) (О" )и — степень числа 2); г) множество цепочек из нулей и единиц, длины которых — полные квадраты; д) множество цепочек из нулей н единиц вида ни, где некоторая цепочка»г по- вторяется дважды; е) множество цепочек нз нулей и единиц вида впг, где за цепочкой следует цепочка, обратная к ней (формальное определение цепочки, обратной к данной, см.
в разделе 4.2.2); ж) множество цепочек из нулей и единиц вида и ж, где цепочка »г образована из»г путем замены всех нулей единицами и наоборот. Например, 011 = 100, так что цепочка 011100 принадлежит данному языку; з) множество цепочек из нулей и единиц вида н1", где и — цепочка из нулей и единиц длиной п. 147 4.1. ДОКАЗАТЕЛЬСТВО НЕРЕГУЛЯРНОСТИ ЯЗЫКОВ 4.1.3. (!!) Докажите нерегулярность следующих языков: а) множество всех цепочек из нулей и единиц, которые начинаются с единицы и удовлетворяют следующему условию: если интерпретировать такую цепочку как целое число, то это число простое б) множество цепочек вида 0'1', для которых наибольший общий делитель чисел ! ну равен !.
4.1.4. (!) При попытке применения леммы о накачке к регулярным языкам "противник выигрывает", и закончить доказательство не удается. Определите, что именно происходит не так, как нужно, если в качестве Е выбрать следующий язык: а) (е) пустое множество; б) (е) (00, !!); в) (е) (00ж11); г) 01*0 1. 4.2. Свойства замкнутости регулярных языков В этом разделе доказано несколько теорем вида "если определенные языки регулярны, а язык Е построен из них с помощью определенных операций (например, Е есть объединение двух регулярных языков), то язык Е также регулярен". Эти теоремы часто на- зывают свойствами замкиузпости регулярных языков, так как в них утверждается, что класс регулярных языков замкнут относительно определенных операций.
Свойства замкнутости выражают идею того, что если один или несколько языков регулярны, то языки, определенным образом связанные с ним (с ними), также регулярны. Кроме того, данные свойства служат интересной иллюстрацией того, как эквивалентные представления регулярных языков (автоматы и регулярные выражения) подкрепляют друг друга в нашем понимании этого класса языков, так как часто один способ представления намного лучше других подходит для доказательства некоторого свойства замкнутости. Основные свойства замкнутости регулярных языков выражаются в том, что эти языки замкнуты относительно следующих операций. !.
Объединение. 2. Пересечение. 3. Дополнение. 4. Разность. 5. Обращение. ' Иными словами, это двоичные записи простых чисел. — Прим. ред. ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 148 Итерация (звездочка). Конкатенация. Гомоморфнзм (подстановка цепочек вместо символов языка). Обратный гомоморфизм. (.2.1. Замкнутость регулярных языков относительно булевых операций Сначала рассмотрим замкнутость для трех булевых операций: обьединение, пересе~еиве и дополнение.
Пусть Е и М вЂ” языки в алфавите Х. Тогда язык Е () М содержит все цепочки, кото- рые принадлежат хотя бы одному из языков Е или М. Е Пусть Е и М вЂ” языки в алфавите Х. Тогда язык Е П М содержит все цепочки, принадлежащие обоим языкам Е и М. Пусть Š— некоторый язык в алфавите Х. Тогда язык Е, дополнение Е, — это мно- жество тех цепочек в алфавите Х, которые не принадлежат Е. Что делать, если языки имеют разные алфавиты? Прн обьединении или пересечении двух языков Е и М может оказаться, что они опре- ~ делены в разных алфавитах.
Например, возможен случай, когда Е~ ~ (а, Ь), а Ез ~ (Ь, с, с). Однако, если язык Е состоит из цепочек символов алфавита Х, то Е можно также рассматривать как язык в любом конечном алфавите, включающем Х (надмножестве Х). Например, можно представить указанные выше языки Е, и Е, как языки в алфавите (а, Ь, с, Е). То, что ни одна цепочка языка Ер не содержит символов с или Ы, несущественно, как и то, что нн одна цепочка языка Ез не содержит а, Аналогично, рассматривая дополнение языка Е, который является подмножеством множества Х~ для некоторого алфавита Хь можно взять дополнение относительно некоторого алфавита Хь включающего Х~ (надмножества Х,).
В этом случае дополнением Е будет Х, — Е, т,е. дополнение языка Е относительно алфавита Х, включает (среди прочих) все цепочки из Х., которые содержат хотя бы один символ алфавита Хь не принадлежащий Хь Если взять дополнение Е относительно Хь то нн одна цепочка, содержащая символы из Хз — Хь не попадет в ).. Таким образом, чтобы избежать неточностей, нужно указывать алфавит, относительно которого берется дополвеиие. Часто, однако, бывает очевидно, какой алфавит подразумевается в конкретном случае.
Например, если язык Е определен некоторым автоматом, то в описании этого автомата указывается и алфавит. Итак, во многих ситуациях можно говорить о "дополнении", не указывая алфавит. 4.2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ 149 Оказывается, что класс регулярных языков замкнут относительно всех трех булевых операций, хотя, как будет видно, в доказательствах используются совершенно разные подходы. Замкнутость относительно обьединении Теорема 4.4.
Если Е и М вЂ” регулярные языки, то?.1) М также регулярен. Доказательство. Поскольку языки Т. и М регулярны, им соответствуют некоторые регулярные выражения. Пусть Т. = ЦВ) и М= ЦВ). Тогда?.1) М = ЦВ + 5) согласно определению операции + для регулярных выражений. ь3 Замкнутость относительно регулярных операций Доказательство замкнутости регулярных выражений относительно объединения было исключительно легким, поскольку объединение является одной из трех операций, определяющих регулярные выражения.
Идея доказательства теоремы 4.4 применима также к конкатенации и итерации. Таким образом, ° если?. и М-- регулярные языки, то язык?М регулярен; ° если?. — регулярный язык, то 2* также регулярен. Замкнутость относительно дополнения Теорема для объединения языков легко доказывается с помощью регулярных выражений. Теперь рассмотрим дополнение. Знаете ли вы, как преобразовать регулярное выражение, чтобы оно определяло дополнение языка? Мы тоже не знаем.
Однако это выполнимо, так как согласно теореме 4.5 можно, начать с ДКА и построить ДКА, допускающий дополнение. Таким образом, начав с регулярного выражения для языка, можно найти выражение для его дополнения следующим образом. 1. Преобразовать регулярное выражение в к-НКА. 2. Преобразовать л-НКА в ДКА с помощью конструкции подмножеств. 3. Дополнить допускающие состояния зтого ДКА. 4. Преобразовать полученный ДКА для дополнения обратно в регулярное выражение, используя методы из разделов 3.2.1 или 3.2.2.
Теорема 4.5. Если Т. — регулярный язык в алфавите а„то язык Х = Š— 2, также регулярен. Доказательство. Пусть |. = ЦА) для некоторого ДКА А = Я, Е, б, дь Е). Тогда Х = ЦВ), где  — это ДКА Я, Е, б, дь Д вЂ” г), т.е. автоматы А и В одинаковы, за исключением того, что допускающие состояния автомата А стали не допускающими в В, и наоборот.
Тогда н принадлежит ЦВ), если, и только если, Б (дь и ) принадлежит Д вЂ” Г, т.е. н не при- надлежитЦА). П ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 150 Заметим, что для приведенного выше доказательства важно, чтобы 6 (пе, зи) всегда было некоторым состоянием. Это значит, что в автомате А все переходы определены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
