dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 32
Текст из файла (страница 32)
С другой стороны, мы можем рекурсивнопостроить ε-НКА по регулярному выражению, а потом в случае необходимостипреобразовать полученный ε-НКА в ДКА.♦ Алгебра регулярных выражений. Регулярные выражения подчиняются многим алгебраическим законам арифметики, хотя есть и различия. Объединение и конкатенация ассоциативны, но только объединение коммутативно. Конкатенация дистрибутивна относительно объединения. Объединение идемпотентно.♦ Проверка истинности алгебраических тождеств. Чтобы проверить эквивалентность регулярных выражений с переменными в качестве аргументов, необходимоподставить вместо этих переменных различные константы и проверить, будут лисовпадать языки, полученные в результате.ÐÅÇÞÌÅСтр. 141141ËèòåðàòóðàИдея регулярных выражений и доказательство их эквивалентности конечным автоматам представлены в работе Клини [3].
Преобразование регулярного выражения в ε-НКАв том виде, как оно выглядит в этой книге, известно как “Метод Мак-Нотона-Ямады” изработы [4]. Проверку тождеств регулярных выражений, в которой переменные рассматриваются как константы, предложил Дж. Гишер [2]. В его отчете, который считаетсяустным, продемонстрировано, как добавление нескольких других операций, например,пересечения или перемешивания (см. упражнение 7.3.4), приводит к ошибочности данной проверки, хотя класс задаваемых языком при этом не изменяется.Еще до появления системы UNIX К.
Томпсон исследовал возможность применениярегулярных выражений в таких командах, как grep, и придуманный им алгоритм выполнения таких команд можно найти в [5]. На ранней стадии развития UNIX появилисьдругие команды, в которых активно использовались расширенные регулярные выражения, например, команда lex, предложенная М. Леском.
Описание этой команды и других технологий, связанных с регулярными выражениями, можно найти в [1].1.A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading MA, 1986. (Ахо А. В., Сети Р., Ульман Дж. Компиляторы:принципы, технологии и инструменты. — М.: Издательский дом “Вильямс”, 2001.)2.J. L. Gisher, STAN-CS-TR-84-1033 (1984).3.S. C. Kleene, “Representation of events in nerve nets and finite automata”, InC. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ.
Press, 1956, pp. 3–42.(Клини С.К. Представление событий в нервных сетях. / сб. “Автоматы”. — М.: ИЛ,1956. — С. 15–67.)4.R. McNaughton and H. Yamada, “Regular expressions and state graphs for automata”,IEEE Trans. Electronic Computers 9:1 (Jan., 1960), pp. 39–47.5.K. Thompson, “Regular expression search algorithm”, Comm. ACM 11:6 (June, 1968),pp. 419–422.142Стр. 142ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈÃËÀÂÀ 4ÑâîéñòâàðåãóëÿðíûõÿçûêîâВ этой главе рассматриваются свойства регулярных языков.
В разделе 4.1 предлагаетсяинструмент для доказательства нерегулярности некоторых языков — теорема, котораяназывается “леммой о накачке” (“pumping lemma”)1.Одними из важнейших свойств регулярных языков являются “свойства замкнутости”.Эти свойства позволяют создавать распознаватели для одних языков, построенных издругих с помощью определенных операций. Например, пересечение двух регулярныхязыков также является регулярным. Таким образом, при наличии автоматов для двухразличных регулярных языков можно (механически) построить автомат, который распознает их пересечение.
Поскольку автомат для пересечения языков может содержать намного больше состояний, чем любой из двух данных автоматов, то “свойство замкнутости” может оказаться полезным инструментом для построения сложных автоматов. Конструкция для пересечения уже использовалась в разделе 2.1.Еще одну важную группу свойств регулярных языков образуют “свойства разрешимости”.
Изучение этих свойств позволяет ответить на важнейшие вопросы, связанные с автоматами. Так, можно выяснить, определяют ли два различных автомата один и тот же язык.Разрешимость этой задачи позволяет “минимизировать” автоматы, т.е. по данному автомату найти эквивалентный ему с наименьшим возможным количеством состояний. Задачаминимизации уже в течение десятилетий имеет большое значение при проектировании переключательных схем, поскольку стоимость схемы (площади чипа, занимаемого схемой)снижается при уменьшении количества состояний автомата, реализованного схемой.4.1.
Äîêàçàòåëüñòâî íåðåãóëÿðíîñòè ÿçûêîâВ предыдущих разделах было установлено, что класс языков, известных как регулярные, имеет не менее четырех различных способов описания. Это языки, допускаемыеДКА, НКА и ε-НКА; их можно также определять с помощью регулярных выражений.Не каждый язык является регулярным. В этом разделе предлагается мощная техникадоказательства нерегулярности некоторых языков, известная как “лемма о накачке”.
Ни1В русскоязычной литературе в свое время был принят термин “лемма о разрастании”. Однако, на наш взгляд, “накачка” точнее отражает суть происходящего. — Прим. ред.Стр. 143же приводится несколько примеров нерегулярных языков. В разделе 4.2 лемма о накачкеиспользуется вместе со свойствами замкнутости регулярных языков для доказательстванерегулярности других языков.4.1.1. Ëåììà î íàêà÷êå äëÿ ðåãóëÿðíûõ ÿçûêîâРассмотрим язык L01 = {0n1n | n ≥ 1}.
Этот язык состоит из всех цепочек вида 01, 0011,000111 и так далее, содержащих один или несколько нулей, за которыми следует такоеже количество единиц. Утверждается, что язык L01 нерегулярен. Неформально, если быL01 был регулярным языком, то допускался бы некоторым ДКА А, имеющим какое-точисло состояний k. Предположим, что на вход автомата поступает k нулей. Он находитсяв некотором состоянии после чтения каждого из k + 1 префиксов входной цепочки, т.е. ε,0, 00, …, 0k. Поскольку есть только k различных состояний, то согласно “принципу голубятни”, прочитав два различных префикса, например, 0i и 0j, автомат должен находится водном и том же состоянии, скажем, q.Допустим, что, прочитав i или j нулей, автомат А получает на вход 1.
По прочтении iединиц он должен допустить вход, если ранее получил i нулей, и отвергнуть его, получивj нулей. Но в момент поступления 1 автомат А находится в состоянии q и не способен“вспомнить”, какое число нулей, i или j, было принято. Следовательно, его можно“обманывать” и заставлять работать неправильно, т.е. допускать, когда он не долженэтого делать, или наоборот.Приведенное неформальное доказательство можно сделать точным. Однако к заключению о нерегулярности языка L01 приводит следующий общий результат.Теорема 4.1 (лемма о накачке для регулярных языков). Пусть L — регулярный язык.Существует константа n (зависящая от L), для которой каждую цепочку w из языка L,удовлетворяющую неравенству |w| ≥ n, можно разбить на три цепочки w = xyz так, чтовыполняются следующие условия.1.y ≠ ε.2.|xy| ≤ n.3.Для любого k ≥ 0 цепочка xykz также принадлежит L.Это значит, что всегда можно найти такую цепочку y недалеко от начала цепочки w, которую можно “накачать”.
Таким образом, если цепочку y повторить любое число раз илиудалить (при k = 0), то результирующая цепочка все равно будет принадлежать языку L.Доказательство. Пусть L — регулярный язык. Тогда L = L(A) для некоторого ДКА A.Пусть A имеет n состояний. Рассмотрим произвольную цепочку w длиной не менее n,скажем, w = a1a2…am, где m ≥ n и каждый ai есть входной символ.
Для i = 0, 1, 2, …, n∧определим состояние pi как δ (q0, a1a2…ai), где δ — функция переходов автомата A, аq0 — его начальное состояние. Заметим, что p0 = q0.144Стр. 144ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂРассмотрим n + 1 состояний pi при i = 0, 1, 2, …, n. Поскольку автомат A имеет n различных состояний, то по “принципу голубятни” найдутся два разных целых числа i и j(0 ≤ i < j ≤ n), при которых pi = pj.
Теперь разобьем цепочку w на xyz.1.x = a1a2…ai.2.y = ai+1ai+2…aj.3.z = aj+1aj+2…am.Таким образом, x приводит в состояние pi, y — из pi обратно в pi (так как pi = pj), аz — это остаток цепочки w. Взаимосвязи между цепочками и состояниями показаны нарис. 4.1.
Заметим, что цепочка x может быть пустой при i = 0, а z — при j = n = m. Однакоцепочка y не может быть пустой, поскольку i строго меньше j.НачалоРис. 4.1. Каждая цепочка, длина которой больше числа состояний автомата,приводит к повторению некоторого состоянияТеперь посмотрим, что происходит, когда на вход автомата A поступает цепочка xykzдля любого k ≥ 0.
При k = 0 автомат переходит из начального состояния q0 (которое естьтакже p0) в pi, прочитав x. Поскольку pi = pj, то z переводит A из pi в допускающее состояние (см. рис. 4.1).Если k > 0, то по x автомат A переходит из q0 в pi, затем, читая yk, k раз циклически проходит через pi, и, наконец, по z переходит в допускающее состояние. Таким образом, длялюбого k ≥ 0 цепочка xykz также допускается автоматом A, т.е. принадлежит языку L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
