Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 36
Текст из файла (страница 36)
Будет ли язык У. регулярным? Докажем, что такой язык регулярен, хотя доказательство довольно сложное. Начнем с языка И= ЦА), т.е. множества цепочек, допускаемых автоматом А обычным путем, независимо от того, в какие состояния он переходит, обрабатывая входную цепочку. Заметим, что Х ~ М, так как определение языка Х накладывает дополнительные ограничения на цепочки из ЦА). Доказательство регулярности языка У.
начинается с использования обратного гомоморфизма лля вставки состояний автомата А во входные символы. Точнее, определим новый алфавит Т как состоящий из символов, которые можно представить в виде троек [расу], где р и су — состояния из Д, а — символ из Х, и а(р, а) = д. Таким образом, символы алфавита Т представляют переходы автомата А. Важно понимать, что запись [раа] представляет собой единый символ, а не конкатенацию трех символов. Можно обозначить этот символ одной буквой, но при этом трудно описать его связь с р, д и а. Теперь определим гомоморфизм Ь([раа]) =- а для всех р, а и д.
Это значит, что гомоморфизм 6 удаляет из каждого символа алфавита Т компоненты, представляющие состояния, и оставляет только символ из Х. Первый шаг доказательства регулярности языка Х состоит в построении языка У,, = Ь ~(ЛУ). Поскольку язык М регулярен, то согласно теореме 4.1б язык У., также регулярен. Цепочками языка С, будут цепочки из И, к каждому символу которых присоелиняется пара состояний, представляющая некоторый переход автомата. В качестве просто~о примера рассмотрим автомат с двумя состояниями, представленный на рис.4.4, а.
Алфавит Х = (О, 1], а алфавит Т состоит из четырех символов [рбмк], [дба], [р1р] и [а!а], Например, поскольку по символу О есть переход из р в а, то [рбмк] — один из символов алфавита Т. Так как цепочка 101 допускается этим автоматом, применив к ней обратный гомоморфизм и ', получим 2' = 8 цепочек, две из которых, например, равны [р1р][рбгу][д1д] и [гу1су][аО(у][р!р]. 1бО ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ Теперь по языку 2, построим язык Ь с помощью ряда операций, сохраняющих регулярность языков.
Наша первая цель — исключить все те цепочки языка Т,ь в которых состояния указаны неправильно. Поскольку каждый символ вида ~рагу1 означает, что автомат был в состоянии р, прочитал а и затем перешел в состояние д, последовательность таких символов, представляющая допускающее вычисление в автомате А, должна удовлетворять следующим трем условиям. Е Первым состоянием в первом символе должно быть гув — начальное состояние А.
2. Каждый переход автомата должен начинаться там, где закончился предыдущий, т.е. пер- вое состояние в символе должно равняться второму состоянию в предыдущем символе. 3. Второе состояние в последнем символе должно принадлежать Р'. Если выполняются первые два условия, то и это условие будет выполнено, поскольку каждая цепочка языка !, образована из цепочки, допускаемой автоматом А. Язык автомата А Обратный гомоморфизм Цепочки языка М, е которые вставлены компоненты состояний Пересечение с регулярным языком Добавить условие, что первым является начальное состояние Разница с регулярным языком Добавить условие, что смежные состояния должны совпадать Разница с регулярными языками Добавить условие, что на пути встречаются есе состояния Гомоморфизм Удалить компоненты состояний, оставляя только символы Рис.
4. 7. Паслграение языка С па языку М с паногцью операций, сохраняющих регулярность языков 4.2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ План построения языка Е представлен на рис. 4.7. Условие 1 обеспечивается пересечением языка Ь, со множеством цепочек, которые начинаются символом вида 170ад] для некоторого символа а и состояния 7. Пусть Е~ — выражение ~д„а,г7,] + (папку~], ..., где ац, — все пары из Х х Д, для которых с(у„а) = ~7,.
Пусть Е, = Ь, П ЦЕ!Т ). Регулярное выражение Е,T обозначает все цепочки из Т, которые начинаются стартовым состоянием (здесь Т можно рассматривать как сумму всех его символов). Поэтому язык Ь, состоит из всех цепочек, полученных в результате применения обратного гомоморфнзма Ь к языку М, у которых первым компонентом в первом символе является начальное состояние, т.е.
язык Ь, удовлетворяет условию 1. Чтобы обеспечить выполнение условия 2, проще всего вычесть из Ь, (используя операцию разности множеств) все цепочки, нарушающие это условие. Пусть Е, — регулярное выражение, состоящее из суммы (объединения) конкатенаций всех пар символов, которые друг другу не подходят.
Это все пары вида ]рагуЦгбз], где ~7 ~ г. Тогда регулярное выражение Т Е,Т обозначает все цепочки, не удовлетворяющие условию 2. Теперь можно определить Еэ = Ез — Ь(Т Е,7'). Цепочки языка Е, удовлетворяют условию 1, поскольку цепочки язьиа Е,. начинаются стартовым состоянием. Они также удовлетворяют условию 2, так как в результате вычитания Е(Т Е,Т ) будут удалены все цепочки, для которых это условие не выполняется. Наконец, они удовлетворяют условию 3 (последнее состояние является допускающим), поскольку доказательство было начато с цепочек языка М, допускаемых автоматом А.
В результате Ь, состоит нз цепочек языка М с состояниями допускающего вычисления такой цепочки, вставленными в каждый символ. Заметим, что язык Еэ регулярен, так как он построен из регулярного языка М с помощью операций обратного гомоморфизма, пересечения и разности множеств, сохра- няющих регулярность.
Напомним, что наша цель состоит в том, чтобы допустить только те цепочки из М при обработке которых автомат проходит через каждое состояние. Выполнение этого условия можно обеспечить с помощью операции разности множеств. Пусть лля каждого состояния и регулярное выражение Е» представляет собой сумму всех символов алфавита Т, в которые не входит состояние д (д не стоит нн на первой, ни на последней позиции). В результате вычитания языка Е(Е,, ) из Е, получим цепочки, представляющие допускающее вычисление автомата А и проходящие через состояние д, по крайней мере, один раз. Если вычесть из Ьэ языки ЦЕ, ) для всех 7 из Д, то получим допускающие вычисления автомата А, проходящие через все состояния.
Обозначим этот язык Ць По теореме 4.10 язык Ь, также регулярен. Последний шаг состоит в построении языка Е из Ь, с помощью исключения компонентов состояний, т.е. Ь = Ь(Е,). Теперь Е является множеством цепочек в алфавите Х, допускаемых автоматом А, причем при их обработке автомат проходит через каждое состояние, по крайней мере, один раз. Поскольку регулярные языки замкнуты относительно гомоморфизмов, делаем вывод, что язык Е регулярен. П 162 ГЛАВА 4.
СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 4.2.5. Чпражнення к разделу 4.2 4.2.1. Пусть 6 — гомоморфизм из алфавита (О, 1,2) в алфавит (а, Ь), определенный как 6(0) = а, Ь(1) = аЬ и Ь(2) = Ьа: а) (в) найдите Ь(0!20); б) найдите 6(21120); в) (н) найдите /т(Е) для Е = Ц01 2); г) найдите Ь(Е) для Е = ЦО -: 12); д) (*) найдите Ь 1(Е) для Е = (аЬаЬа), т.е. языка, состоящего из одной- единственной цепочки аЬаЬа; е) (!) найдите Ь 1(Е) для Е= Ца(Ьа) ). 4.2.2. (н!) Если Š— язык, а — символ, то Е(а, частное Е и а, — это множество цепочек н, для которых жа принадлежит Е. Например, если Е = (а, ааЬ, Ьаа), то Е(а = (е, Ьа).
Докажите, что из регулярности Е следует регулярность Е(а. Уктание. Начните с ДКА для Е и рассмотрите множество допускающих состояний. 4.2.3. (!) Если Š— язык, а — символ, то а1Š— это множество цепочек ж, для которых ач принадлежит Е. Например, если Е = (а, ааЬ, Ьаа), то а1Е = (к, аЬ), Докажите, что из регулярности Е следует регулярность а1Е. Указание. Вспомните, что регулярные языки замкнуты относительно обращения и операции деления из упражнения 4.2.2. 4,2.4. (!) Какие из следующих тождеств истинны? а) (Е(а)а = Е (в левой части представлена конкатенация языков Е(а и (а)).
б) а(а1Е) = Е (снова представлена конкатенация с языком (а), но на этот раз слева). в) (Еа)(а = Е. г) а1(аЕ)=Е. 4.2.5. Операция из упражнения 4.2.3 иногда рассматривается как "производная", а выра- Ж жение а!Е записывается как —. Эти производные применяются к регулярным Иа выражениям аналогично тому, как обычные производные применяются к арифметическим выражениям. Таким образом, если (1 — регулярное выражение, то Ы г(Š— обозначает то же, что и —, если Е = Ц(1); Иа да И(А + 5) с((1 Н5 а) докажите„что — = — ь— г(а Ыа г(а б) (н!) напишите правило для "производной*' от (ьэ. Указание. Нужно рассмотреть два случая: язык ЦЯ) включает нли не включает цепочку е.
Это правило 1.2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ 163 не совпадает с "правилом произведения" для обычных производных, но похоже на него; ы()1*) в) (!) найдите "производную'* от итерации, т.е, с!а г) используя формулы (а)-(в), найдите производную регулярного выражения (0 + 1) 011; с!Е д) (в) опишите такие языки Е, для которых — = Я; Ю Ы, е) (ь!) опишите такие языки Е, для которых — = Е. Ю 4.2.6. (!) Докажите замкнутость регулярных языков относительно следующих операций: а) и!л(Е) = !и ) ж принадлежит Е, но ии один собственный префикс цепочки ж не принадлежит Ц; б) тат(Е) = !ж!и принадлежитЕ, иодля любого х~ в цепочка згх не принадлежит Ц; в) ГтЩ = 1ж ! лля некоторого х цепочка згх принадлежит Ц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
