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

3.2.4. Упражнения к разделу 3.2

3.2.1. ДКА представлен следующей таблицей переходов:

0	1
~><7i	Яг	<7i
42	<7з	<7i
*<7з	<7з	42

а)        (*) выпишите все регулярные выражения. Замечание. Состояние с/, мож­но рассматривать как состояние с целым номером /;

б)        (*) выпишите все регулярные выражения. Постарайтесь максимально упростить эти выражения;

в)        выпишите все регулярные выражения R(2). Постарайтесь максимально упро­стить эти выражения;

г)        напишите регулярное выражение для языка заданного автомата;

д)        (*) постройте диаграмму переходов для этого ДКА и напишите регулярное выражение для его языка, исключив состояние q2.

3.2.2. Повторите упражнение 3.2.1 для следующего ДКА.

0	1
~><7i	Яг	<7з
42	<7i	<7з
*<7з	Яг	Я\

Отметим, что решения для пунктов а, 6 и д непригодны в данном упражнении. 3.2.3. Преобразуйте следующий ДКА в регулярное выражение, используя технику ис­ключения состояний из раздела 3.2.2.

0	1
—> *р	s	Р
ч	р	s
г	г	Ч
s	Я	г

Преобразуйте следующие регулярные выражения в НКА с Ј-переходами;

а)        (*) 01*;

б)        (0+ 1)01; в) 00(0+1)*.

Исключите e-переходы из НКА, полученных вами в упражнении 3.2.4. Решение для пункта а можно найти на Web-страницах этой книги. (!) Пусть А = (Q, Ј, <5, q0, {<7f}) — это такой Ј-НКА, в котором нет переходов в состояние q0 и из состояния с/{. Опишите язык, допускаемый каждой из следую­щих модификаций автомата А (в терминах языка L = L(A))\

а)        (*) автомат, образованный по А путем добавления ^-перехода из q{ в д0;

б)        (*) автомат, построенный по А с помощью добавления е-перехЬда из состоя­ния q0 в каждое состояние, достижимое из д0 (по путям, метки которых могут содержать как символы из Ј, так и е);

в)        автомат, полученный по А посредством добавления ^-перехода в qf из каждо­го состояния, из которого по какому-либо пути достижимо с/г;

г)        автомат, построенный по А путем одновременного выполнения пунктов бив.

(!!) Существует несколько упрощений конструкции теоремы 3.7, в которой ре­гулярное выражение преобразовывалось в g-НКА. Вот три из них. Для оператора объединения вместо создания новых начального и допус­кающего состояний можно сгруппировать оба начальных состояния в одно, сохранив все их переходы. Аналогично, можно сгруппировать оба допус­кающих состояния в одно; к нему ведут все переходы, которые вели к каж­дому из исходных состояний. Для оператора конкатенации можно объединять допускающее состояние первого автомата с начальным состоянием второго. Для оператора итерации можно просто добавить ^-переходы из допускающе­го состояния в начальное, и наоборот.

В результате каждого из этих упрощений мы по-прежнему получаем правиль­ную конструкцию, т. е. искомый е-НКА, который для любого регулярного выра­жения допускает язык этого выражения. Сочетание каких усовершенствований (1, 2 или 3) можно применить к этой конструкции, чтобы в результате получался правильный автомат для любого регулярного выражения?

3.2.8. (*!!) Постройте алгоритм, который по данному ДКА А вычисляет количество цепочек длины п, допускаемых ДКА А (п не связано с количеством состояний автомата А). Ваш алгоритм должен быть полиномиальным как относительно п, так и относительно количества состояний А. Указание. Используйте технику, предложенную в доказательстве теоремы 3.4.

3.3. Применение регулярных выражений

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

3.3.1. Регулярные выражения в UNIX

Прежде чем рассмотреть данные приложения, ознакомимся с системой обозначений, используемой в UNIX для расширенных регулярных выражений. Эти обозначения пре­доставляют много дополнительных возможностей. На самом деле, расширения UNIX включают некоторые особенности, в частности, возможность именовать и ссылаться на предыдущие цепочки, соответствующие шаблону, что, фактически, позволяет распозна­вать нерегулярные языки. Здесь эти особенности не рассматриваются, но вводятся со­кращения, позволяющие записывать сложные регулярные выражения в сжатом виде.

Первое усовершенствование в системе обозначений регулярных выражений связано с тем, что большинство приложений работает с символами в коде ASCII. В наших приме­рах обычно использовался алфавит {0, 1). Наличие только двух символов позволяет ис­пользовать сокращенные выражения вроде 0 + 1 для обозначения "любого символа". Од­нако если алфавит состоит, скажем, из 128 символов, то аналогичное выражение вклю­чало бы список всех этих символов и стало бы весьма неудобным для написания. Таким образом, регулярные выражения в UNIX позволяют задавать классы символов для пред­ставления множеств символов в наиболее кратком виде. Существуют следующие прави­ла для классов символов.

Символ. (точка) обозначает "любой символ". Последовательность [а^-.-а^] обозначает регулярное выражение а{ + а2 + ... + ак

Такое обозначение позволяет записывать примерно вдвое меньше символов, по­скольку нет необходимости писать знак "+". Например, четыре символа, исполь­зуемые в операторах сравнения языка С, можно выразить в виде [<>= ! ].

В квадратных скобках записывается диапазон вида х—у для обозначения всех символов от х до у из последовательности символов в коде ASCII. Поскольку ко­ды цифр, а также символов верхнего и нижнего регистров упорядочены, то мно­гие важные классы символов можно записывать с помощью нескольких ключе­вых цепочек. Например, все цифры могут быть представлены в виде [0-9], символы верхнего регистра могут быть выражены как [A-Z], а множество всех букв и цифр можно записать как [A-Za-z0-9]. Если необходимо включить в такой список символов знак минуса, то его помещают в самом начале или в са­мом конце списка, чтобы не было путаницы с использованием его для обозначе­ния диапазона символов. Например, набор цифр вместе с точкой и знаками плюс и минус, используемый для образования десятичных чисел со знаком, можно за­писать в виде выражения [-+.0-9]. Квадратные скобки и другие символы, имеющие специальные значения в регулярных выражениях UNIX, задаются в ка­честве обычных символов с помощью обратной косой черты (\)перед ними. Для некоторых наиболее часто используемых классов символов введены специ­альные обозначения. Рассмотрим несколько примеров:

а)        [: digit: ] обозначает множество из десяти цифр, как и [ 0-9]5;

б)        [: alpha: ] обозначает любой символ (латинского) алфавита, как и [ A-Za-z ];

в)        [ :alnum: ] обозначает все цифры и буквы (буквенные и цифровые симво­лы), как и [A-Za-z0-9].

Кроме того, в регулярных выражениях UNIX используется несколько операторов, с которыми мы раньше не сталкивались. Ни один из этих операторов не расширяет мно­жество выражаемых языков, но иногда облегчает выражение того, что нам нужно.

Оператор | используется вместо + для обозначения объединения. Оператор? значит "ни одного или один из". Таким образом, R? в UNIX означает то же, что и Ј + R в системе записи регулярных выражений, принятой в этой книге. Оператор + значит "один или несколько из". Следовательно, R+ в UNIX является со­кращением для RR* в наших обозначениях.

4. Оператор {п} обозначает "и копий". Таким образом, R{5} в UNIX является сокра­щенной записью для RRRRR в наших обозначениях.

Отметим, что в регулярных выражениях UNIX для группирования подвыражений ис­пользуются скобки, как и в регулярных выражениях из раздела 3.1.2, и тот же порядок при­оритетов операторов (в этом смысле?, + и {п} трактуются как *). Оператор * используется в UNIX (конечно же, не как верхний индекс) в рассмотренном выше значении.

3.3.2. Лексический анализ

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

Полное описание регулярных выражений в UNIX

Читатель, желающий ознакомиться с полным списком операторов и сокращений, используемых в системе записи регулярных выражений в UNIX, может найти их на учебных страницах для различных команд. Существуют некоторые различия между версиями UNIX, но команда типа man grep выдаст вам обозначения, ис­пользуемые для команды grep, которая является основной. Кстати, "grep" озна­чает "Global (search for) Regular Expression and Print" (Глобальный поиск регуляр­ного выражения и печать).