XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 86
Текст из файла (страница 86)
Ь Рассмотрим теперь некоторые примеры доказательств нерегулярности языка с использованием леммы о разрастании. Стандартный ход рассуждений при решении таких задач состоит в предположении регулярности данного языка и последующем анализе возможности представить любую достаточно длинную цепочку языка в виде, указанном в условии леммы о разрастании. Анализируя все возможные случаи размещения „накачиваемой" подцепочки о, мы должны получить противоречие. Пример 7.12. а. Докажем нерегулярность языка Ь1 = (а"Ь": и > О) .
Выбирая и настолько большим, чтобы оно превосходило йу, (константу леммы), получаем следующие возможные случаи размещения средней подцепочки о в цепочке а"Ь". 1. о = а', л < и, т.е. „накачиваемая" надцепочка целиком располагается в „зоне символов а" (рис. 7.30, а).
Ясно, что накачка в этом случае выведет за пределы языка, так как при повторении цепочки о число символов а будет неограниченно расти, а число символов Ь будет оставаться прежним. 7.В. Левил о рлзраетллли длл регуллрыыл лэылол 541 Рис. 7.30 2. о = Ь*, з < и, т.е. „накачиваемая" подцепочка целиком располагается в „зоне символов Ь" (рис.
7.30, б). Накачка невозможна по той же причине, что и в предыдущем случае. 3. о = аРЬе, где 0 < р < и, О < д < и, т.е. „накачиваемая л подцепочка находится „на стыке зон символов а и Ь" (рис. 7.30, в). В этом случае при накачке возникнет вхождение подцепочки Ьа в слово, которое, следовательно, уже не принадлежит язьпсу Ь1. Таким образом, рассматриваемый язык нерегулярен.
б. Докажем, что язык 1'г = Ь', где Ь1 = (аоЬ": и ) О), нерегулярный. Полагая, что язык 1 э регулярен, возьмем слово (а"Ьо)о' для достаточно большого и (т ) 1). Применяя такую же схему рассуждений, как и вьппе, легко убеждаемся в том, что цепочка е не может состоять из одних символов а или из одних символов Ь. Пусть о = а"Ье, где т + з < и. Тогда, повторив цепочку о два раза получим сл в ~ по Ф'о3'ЬлотЬЗЬо е Ясли г ф з го цепочка такого вида не может принадлежать языку 1э, так как в любом слове этого языка эа подцепочкой символов а следует подцепочка символов Ь такой же длины. Но даже если г = з, то получим подцецочку а"Ь', где з < и (или а"Ь", г < и), что также противоречит определению языка Хз. Аналогично рзссматриваетсл случай е = Ь'а' (г+ з < и) (рис.
7.31). 542 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Рис. 7.31 Заметим, что в силу ограничения по длине на цепочку и никакие способы ее размещения в указанной цепочке языка Ьз, кроме описанных вьппе, не возможны. 1$ Полезно иметь в виду следствие из леммы о разрастании. Следствие 7.4.
Если Ь вЂ” бесконечный регулярный язык, то в нем найдется последовательность слов, длины которых образуют возрастающую арифметическую прогрессию. < В качестве такой последовательности можно взять последовательность слов х„из формулировки леммы о разрастании.
Их длины образуют арифметическую прогрессию со знаменателем ~е~ (длина „накачиваемой" средней подцепочки). ~ь Отсюда легко получается вывод о том, что не являются регулярными следующие языки: 1) (а": и ) 01 — язык в однобуквенном алфавите, длины слов которого являются полными квадратами; 2) 1а": р — простое число). Можно доказать, что любой конечный язык регулярен и, более того, допускается конечным автоматом без контуров. Значит, последовательность цепочек, указанная в формулировке леммы, в таком случае не существует, но утверждение леммы остается истинным.
Нужно всегда помнить простое логическое правило: утверждение вида „если А, то Б" равносильно утверждению вида „не А или Б". В заключение обсудим еще одну схему доказательства нерегулярности языка с использованием как леммы о разрастании, так и алгебраических свойств класса регулярных языков, которые были установлены в 7.6.
7.8. Лемма о разрастании дяя регулярных языков 543 Пример 7.13. Докажем нерегулярность языка правильных скобочных структур, порождаемых КС-грамматикой ((()) М ~ Ф-~()!ФИ~Я) (см. грамматику Сз в примере 7.5). Для доказательства поступим так: рассмотрим пересечение данного языка с регулярным языком (" )', который содержит все цепочки вида (вз)а для любых натуральных тп, и > О. Поскольку каждая правильная скобочнал структура содержит одинаковое число символов в(" и „) ", то указанное пересечение будет языком ((" )": и > 01. Если обозначить через а „открывающую скобку" (символ „("), а через Ь „закрывающую скобку" (символ „)"), то получим язык Ьм который, как только что доказано, не является регулярным. Следовательно, предполагая регулярность языка правильных скобочных структур, мы вынуждены будем допустить и регулярность языка Ьм так как пересечение регулярных языков в силу следствия 7.3 регулярно.
Полученное противоречие и доказывает нерегулярность исходного языка. Заметим, что доказательство этого факта с использованием одной лишь леммы о разрастании было бы весьма затруднительно. Замечание 7,12. С использованием „техники пересечения" можно доказать нерегулярность языка Ь| из примера 7.12 следующим образом. Так как язык Ь| = Х г П а'Ь' = (а"Ьв: и > 0) нерегулярный, то и язык Ьз тоже не является регулярным. Итак, можно вывести такой „рецепт": если возникают существенные затруднения в доказательстве нерегулярности какого-либо языка с помощью только леммы о разрастании, то можно попытаться пересечь этот язык с некоторым регулярным языком так, чтобы нерегулярность пересечения легко доказывалась с использованием леммы о разрастании. 544 х кОнечные АВтОмАты и РеГУлЯРные Языки Дополнение 7,1. Обоснование алгоритма детерминизации конечных автоматов В этом дополнении мы подробно докажем корректность приведенного в доказательстве теоремы 7.7 о детерминизации алгоритма построения по заданному конечному ав1помату эквивалентного ему детерминированного конечного автомата.
Сначала докажем корректность алгоритма удаления Л-переходов, после чего подобное доказательство проведем уже для самого алгоритма детерминизации. состояние р Е Я', что в М имеет место р =э~ д, т.е. либо р = о, либо в М существует путь ненулевой длины по пустым дугам из р в о: р ~+ о (на рис. 7.32 и на аналогичных следующих рисунках мы соединяем тонкой штриховой лини- О*® ей кружки, изображающие одно и то же состояние, которое остается после удаления Л-переходов). Возможны два случая для состояния д Е ф оно или остается Рис. Т.ЗЗ 1. Корректность алгоритма удаления Л-переходов. Пусть М = (У, ф дв, г', д) — исходный конечный автомат, а М' = (У, Я',дв, Г',б') — конечный автомат без Л-переходов, построенный согласно алгоритму, описанному в доказательстве теоремы 7.7 о двтерминизации.
Мы должны доказать, что Ь(М) = Ь(М'). а. Докажем, что для любых цепочки х е У' и состояния д Е Я из того, что в конечном автомате М цепочка х читается на некотором пути иэ до в д, т.е. имеет место ов =ь,'. д, следует, что в конечном автомате М' эта цепочка читается на некотором пути из дв в такое Д.7.1. Обосвоиавие аагоритма детармииизавии 545 после удаления Л-переходов, т.е.
д Е Я', либо удаляется в результате удаления Л-переходов,т.е. д ф Ч'. 1'. Состояние д остается после удаления Л-переходов, т.е. 96 Я' Проведем индукцию по длине пути в конечном автомате М, на котором читается цепочка х. Для пути нулевой длины доказываемое тривиально. Пусть для всех й < и — 1 доказываемое свойство имеет место, и пусть цепочка х читается в М на некотоРом пУти Длины п из 9О в д, т.е. 9О =Уоа д. ТогДа сУществУет такое состояние г Е Я, что в М имеет место (7.9) причем х = уа и а Е у'0 (Л). Если а = Л, то х = д, и тогда цепочка х читается в конечном автомате М на некотором пути длины п — 1. При г Е Я' остается только использовать индукционное предположение, и тогда найдется такое состояние г' Е Я', что в М' дО ~' г' и в М г' ~л г, но так как в М г ~1, д, то в М выполняется г' =«~~ 9 (рис.
7.33). Таким образом, мы, исходя из условия, что в М де ~" д, нашли такое состояние т' Е Я', что в М' имеет место до =у' г', а при этом в М выполняется г' =у~+ д, что и требовалось доказать. Рис. '7.33 . и — пни~ 546 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Пусть теперь г ф ЬГ', т.е. состояние г удаляется при удалении А-переходов. Это значит, что в состояние г заходят только дуги с меткой А. Но поскольку на некотором пути из де в г в конечном автомате М читается цепочка у, то найдется такое состояние р Е Я', что в М де ~'„" р ~А г, и т < и — 1 (в частности, может быть ш = 0 и тогда р = де).
Согласно предположению индукции> отсюда следует, что в М' 9е =~„" р', где р' =~), р в М, а так как в М имеет место р =~х г -+А д, то в М р' =~~+ д (рис. 7.34), и мы снова, исходя из условия, что в М де =~" д, нашли в Я' такое состояние р', что цепочка х читается в М' на некотором пути из начального состояния в р', при том что в исходном конечном автомате М иэ этого состояния р' ведет путь по пустым дугам в состояние 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
