Регулярные выражения и языки (стр. 10 )

г)        (R+S)*S=(R'S)*;

д) S(RS + S)'R = RR'S(RR'S)'.

В примере 3.6 было построено регулярное выражение (О + 1)*1(0 + 1) + (0 + 1)*1(0 + 1)(0 + 1).

С помощью дистрибутивных законов преобразуйте его в два различных, более простых, эквивалентных выражения.

В начале раздела 3.4.6 приведена часть доказательства того, что (L*м')' = (L + М) . Завершите это доказательство, показав, что все цепочки из (Ј*Л/)* принадлежат также (L + М) . (!) Завершите доказательство теоремы 3.13 для случаев, когда регулярное выра­жение Е представляет собой FG или F*.

Резюме

Регулярные выраженш. Этот алгебраический способ описания задает те же языки, что и конечные автоматы, а именно, регулярные языки. Регулярными операторами являются объединение, конкатенация ("точка") и итерация ("звездочка"). Регулярные выраженш на практике. Системы, подобные UNIX, и различные их команды используют язык расширенных регулярных выражений, существенно уп­рощающий записи многих обычных выражений. Классы символов позволяют лег­ко записывать выражения для наборов символов, а такие операторы, как "один или несколько из" и "не более, чем один из", расширяют круг обычных регуляр­ных операторов. Эквивалентность регулярных выражений и конечных автоматов. Произвольный ДКА можно преобразовать в регулярное выражение с помощью индуктивной про­цедуры, в которой последовательно строятся выражения для меток путей, прохо­дящих через постепенно увеличивающиеся множества состояний. В качестве аль­тернативы преобразованию ДКА в регулярное выражение можно также использо­вать метод исключения состояний. С другой стороны, мы можем рекурсивно построить е-НКА по регулярному выражению, а потом в случае необходимости преобразовать полученный е-НКА в ДКА. Алгебра регулярных выражений. Регулярные выражения подчиняются многим ал­гебраическим законам арифметики, хотя есть и различия. Объединение и конкате­нация ассоциативны, но только объединение коммутативно. Конкатенация дист­рибутивна относительно объединения. Объединение идемпотентно. Проверка истинности алгебраических тождеств. Чтобы проверить эквивалент­ность регулярных выражений с переменными в качестве аргументов, необходимо подставить вместо этих переменных различные константы и проверить, будут ли совпадать языки, полученные в результате.

Литература

Идея регулярных выражений и доказательство их эквивалентности конечным автома­там представлены в работе Клини [3]. Преобразование регулярного выражения в Ј-НКА в том виде, как оно выглядит в этой книге, известно как "Метод Мак-Нотона-Ямады" из работы [4]. Проверку тождеств регулярных выражений, в которой переменные рассмат­риваются как константы, предложил Дж. Гишер [2]. В его отчете, который считается устным, продемонстрировано, как добавление нескольких других операций, например, пересечения или перемешивания (см. упражнение 7.3.4), приводит к ошибочности дан­ной проверки, хотя класс задаваемых языком при этом не изменяется.

Еще до появления системы UNIX К. Томпсон исследовал возможность применения регулярных выражений в таких командах, как grep, и придуманный им алгоритм вы­полнения таких команд можно найти в [5]. На ранней стадии развития UNIX появились другие команды, в которых активно использовались расширенные регулярные выраже­ния, например, команда lex, предложенная М. Леском. Описание этой команды и дру­гих технологий, связанных с регулярными выражениями, можно найти в [1].

А. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Ad­dison-Wesley, Reading MA, 1986. (, Сети P., Ульман Дж. Компиляторы: принципы, технологии и инструменты. — М.: Издательский дом "Вильяме", 2001.) J. L. Gisher, STAN-CS-TR-84-1033 (1984). S. С. Kleene, "Representation of events in nerve nets and finite automata", In С. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp. 3-42. ( Представление событий в нервных сетях. / сб. "Автоматы". — М.: ИЛ, 1956, — С. 15-67.) R. McNaughton and Н. Yamada, "Regular expressions and state graphs for automata", IEEE Trans. Electronic Computers 9:1 (Jan., 1960), pp. 39-47. K. Thompson, "Regular expression search algorithm", Comm. ACM 11:6 (June, 1968), pp. 419-422.

ГЛАВА 4

Свойства регулярных языков

В этой главе рассматриваются свойства регулярных языков. В разделе 4.1 предлагается инструмент для доказательства нерегулярности некоторых языков — теорема, которая называется "леммой о накачке" ("pumping lemma")8.

Одними из важнейших свойств регулярных языков являются "свойства замкнутости". Эти свойства позволяют создавать распознаватели для одних языков, построенных из других с помощью определенных операций. Например, пересечение двух регулярных языков также является регулярным. Таким образом, при наличии автоматов для двух различных регулярных языков можно (механически) построить автомат, который распо­знает их пересечение. Поскольку автомат для пересечения языков может содержать на­много больше состояний, чем любой из двух данных автоматов, то "свойство замкнуто­сти" может оказаться полезным инструментом для построения сложных автоматов. Кон­струкция для пересечения уже использовалась в разделе 2.1.

Еще одну важную группу свойств регулярных языков образуют "свойства разрешимо­сти". Изучение этих свойств позволяет ответить на важнейшие вопросы, связанные с авто­матами. Так, можно выяснить, определяют ли два различных автомата один и тот же язык. Разрешимость этой задачи позволяет "минимизировать" автоматы, т. е. по данному автома­ту найти эквивалентный ему с наименьшим возможным количеством состояний. Задача минимизации уже в течение десятилетий имеет большое значение при проектировании пе­реключательных схем, поскольку стоимость схемы (площади чипа, занимаемого схемой) снижается при уменьшении количества состояний автомата, реализованного схемой.

4.1. Доказательство нерегулярности языков

В предыдущих разделах было установлено, что класс языков, известных как регуляр­ные, имеет не менее четырех различных способов описания. Это языки, допускаемые ДКА, НКА и Ј-НКА; их можно также определять с помощью регулярных выражений.

Не каждый язык является регулярным. В этом разделе предлагается мощная техника доказательства нерегулярности некоторых языков, известная как "лемма о накачке". Ни­же приводится несколько примеров нерегулярных языков. В разделе 4.2 лемма о накачке используется вместе со свойствами замкнутости регулярных языков для доказательства нерегулярности других языков.

4.1.1. Лемма о накачке для регулярных языков

Рассмотрим язык Ln, = {0"Г | п > 1}. Этот язык состоит из всех цепочек вида 01, 0011, 000111 и так далее, содержащих один или несколько нулей, за которыми следует такое же количество единиц. Утверждается, что язык L0, нерегулярен. Неформально, если бы L(,i был регулярным языком, то допускался бы некоторым ДКА А, имеющим какое-то число состояний к. Предположим, что на вход автомата поступает к нулей. Он находится в некотором состоянии после чтения каждого из к + 1 префиксов входной цепочки, т. е. е,

00, ..., 0к. Поскольку есть только к различных состояний, то согласно "принципу голу­бятни", прочитав два различных префикса, например, О1 и О1, автомат должен находится в одном и том же состоянии, скажем, q.

Допустим, что, прочитав / или j нулей, автомат А получает на вход 1. По прочтении / единиц он должен допустить вход, если ранее получил / нулей, и отвергнуть его, получив j нулей. Но в момент поступления 1 автомат А находится в состоянии q и не способен "вспомнить", какое число нулей, i или /, было принято. Следовательно, его можно "обманывать" и заставлять работать неправильно, т. е. допускать, когда он не должен этого делать, или наоборот.

Приведенное неформальное доказательство можно сделать точным. Однако к заклю­чению о нерегулярности языка L0i приводит следующий общий результат.

Теорема 4.1 (лемма о накачке для регулярных языков). Пусть L — регулярный язык. Существует константа п (зависящая от L), для которой каждую цепочку w из языка L, удовлетворяющую неравенству \w\ > п, можно разбить на три цепочки w = xyz так, что выполняются следующие условия.

уф е. \ху\ < п. Для любого к > 0 цепочка xykz также принадлежит L.

Это значит, что всегда можно найти такую цепочку у недалеко от начала цепочки w, ко­торую можно "накачать". Таким образом, если цепочку у повторить любое число раз или удалить (при к = 0), то результирующая цепочка все равно будет принадлежать языку L.

Доказательство. Пусть L — регулярный язык. Тогда L = L(A) для некоторого ДК А имеет п состояний. Рассмотрим произвольную цепочку w длиной не менее п, скажем, w = а, а2...ат, где т>п и каждый а, есть входной символ. Для /= 0, 1, 2, ...,« определим состояние р, как 8 (с/,,. а/От...а,), где 8— функция переходов автомата А, а qo — его начальное состояние. Заметим, что р0 = qo.

Рассмотрим п + 1 состояний pt при i = О, 1,2, ..., п. Поскольку автомат А имеет п раз­личных состояний, то по "принципу голубятни" найдутся два разных целых числа / и j (0<i<j< п), при которых р, = рг Теперь разобьем цепочку w на xyz.

х = а^.-.а,. у = al+ia,.2---cij. z = а)Ча^2---ат-

Таким образом, х приводит в состояние р„ у — из р, обратно в р, (так как р, = pj), а z — это остаток цепочки w. Взаимосвязи между цепочками и состояниями показаны на рис. 4.1. Заметим, что цепочка х может быть пустой при / = 0, a z — при j = п = т. Однако цепочка у не может быть пустой, поскольку / строго меньше j.

У = а!+, ... о,

X =        '".        2 =

Начало ^-ч        -Ч/^V        V -        /^S

-М^)                *\J

Рис. 4.1. Каждая цепочка, длина которой больше числа состояний автомата, приводит к повторению некоторого состояния