Реферат (стр. 2 )

Существует простой метод проверки, является или нет заданный язык регулярным. Этот метод основан на проверке так называемой леммы о разрастании языка. Доказано, что если для некоторого заданного языка выполняется лемма о разрастании регулярного языка, то этот язык является регулярным; если же лемма не выполняется, то и язык регулярным не является.

Лемма о разрастании для регулярных языков формулируется следующим образом: если дан регулярный язык и достаточно длинная цепочка символов, принадлежащая этому языку, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким способом новые цепочки будут принадлежать тому же регулярному языку. (Если найденную подцепочку повторять несколько раз, то исходная цепочка как бы «разрастается» - отсюда и название «лемма о разрастании языков»).

Формально эту лемму можно записать так: если дан язык L, то ? константа р > 0, такая, что если ??L и |?| ? р, то цепочку ? можно записать в виде ? = ???, где 0 < |?| < р, и тогда ?' = ??i?, ?'?L ?i ? 0.

Используя лемму о разрастании регулярных языков, докажем, что язык L = {аnЬn | n > 0} не является регулярным.

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка ? = аnЬn и запишем ее в виде ? = ???. Если ??a+ или ??b+ то тогда для i = 0 цепочка ??0? = ?? не принадлежит языку L, что противоречит условиям леммы; если же ??a+b+, тогда для i = 2 цепочка ??2? = ???? не принадлежит языку L. Таким образом, язык L не может быть регулярным языком.

1.3. Взаимосвязь регулярных множеств, регулярных грамматик и конечных автоматов

Регулярные выражения и регулярные грамматики связаны между собой следующим образом:

-для любого регулярного языка, заданного регулярным выражением, можно построить регулярную грамматику, определяющую тот же язык;

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

Регулярные выражения и недетерминированные конечные автоматы связаны между собой следующим образом:

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

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

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

Связь регулярных грамматик и конечных автоматов

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

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

Для построения конечного автомата на основании известной грамматики и для построения грамматики на основании данного конечного автомата используются достаточно простые алгоритмы.

Все языки программирования определяют нотацию записи «слева направо». В той же нотации работают и компиляторы. Поэтому далее рассмотрены алгоритмы для леволинейных грамматик.

Построение конечного автомата на основе леволинейной грамматики

Пусть имеется леволинейная грамматика G(VT, VN, P,S), необходимо построить эквивалентный ей конечный автомат M(Q, V,?, qo, F).

Прежде всего для построения автомата исходную грамматику G необходимо привести к автоматному виду. Известно, что такое преобразование можно выполнить для любой регулярной грамматики. Алгоритм преобразования к автоматному виду был рассмотрен выше, поэтому здесь на данном вопросе останавливаться нет смысла. Можно считать, что исходная грамматика G уже является леволинейной автоматной грамматикой.

Тогда построение конечного автомата M(Q, V,?, qo, F) на основе грамматики G(VT, VN, P, S) выполняется по следующему алгоритму.

Шаг 1. Строим множество состояний автомата Q, Состояния автомата строятся таким образом, чтобы каждому нетерминальному символу из множества VN грамматики G соответствовало одно состояние из множества Q автомата М. Кроме того, во множество состояний автомата добавляется еще одно дополнительное состояние, которое будем обозначать Н. Сохраняя обозначения нетерминальных символов грамматики G, для множества состояний автомата М можно записать:

Q=VN?{H}.

Шаг 2. Входным алфавитом автомата М является множество терминальных символов грамматики G: V = VT.

Шаг 3. Просматриваем все множество правил исходной грамматики.

Если встречается правило вида A>t?P, где A?VN, t?VT, то в функцию переходов ?(H, t) автомата М добавляем состояние A: A??(H, t).

Если встречается правило вида A>Bt?P, где A, B?VN, t?VT, то в функцию переходов ?(B, t) автомата М добавляем состояние A: A??(B, t).

Шаг 4. Начальным состоянием автомата М является состояние Н: qo = Н.

Шаг 5. Множество конечных состояний автомата М состоит из одного состояния. Этим состоянием является состояние, соответствующее целевому символу грамматики G: F = {S}.

На этом построение автомата заканчивается.

Построение леволинейной грамматики на основе конечного автомата

Имеется конечный автомат M(Q, V, ?, qo, F), необходимо построить эквивалентную ему леволинейную грамматику G(VT, VN, P, S).

Построение выполняется по следующему алгоритму.

Шаг 1. Множество терминальных символов грамматики G строится из алфавита входных символов автомата М: VT = V.

Шаг 2. Множество нетерминальных символов грамматики G строится на основании множества состояний автомата М таким образом, чтобы каждому состоянию автомата, за исключением начального состояния, соответствовал один нетерминальный символ грамматики: VN = Q\{qo}.

Шаг 3. Просматриваем функцию переходов автомата М для всех возможных состояний из множества Q для всех возможных входных символов из множества V.

Если имеем ?(A, t) = ?, то ничего не выполняем.

Если имеем ?(A, t) = {B1,B2,...,Bn}, n >0, где A?Q, ?n?i?0: Bi?Q, t?V, тогда для всех состояний Вi выполняем следующее:

добавляем правило Bi>t во множество Р правил грамматики G, если А = qo;

добавляем правило Bi>At во множество Р правил грамматики G, если A ? qo.

Шаг 4. Если множество конечных состояний F автомата М содержит только одно состояние F = {F0}, то целевым символом S грамматики G становится символ множества VN, соответствующий этому состоянию: S = Fo; иначе, если множество конечных состояний F автомата М содержит более одного состояния F = {F1, F2,...,Fn}, n>1, тогда во множество нетерминальных символов VN грамматики G добавляется новый нетерминальный символ S: VN = VN?{S}, а во множество правил Р грамматики G добавляются правила: S>F1 | F2 | ... | Fn.

На этом построение грамматики заканчивается.

ГЛАВА 2. ПРАКТИКА СОЗДАНИЯ ГРАММАТИКИ ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ И ПОСТРОЕНИЕ ДЕРЕВА ВЫВОДА

2.1. Состав и синтаксис регулярных выражений

Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите ? определены следующие константы:

(пустое множество) ?.

(пустая строка) ? обозначает строку, не содержащую ни одного символа. Эквивалентно «».

(символьный литерал) «a», где a - символ алфавита ?.

и следующие операции:

(сцепление, конкатенация) RS обозначает множество {?? | ? ? R & ? ? S}. Например, {"boy", "girl"}{"friend", "cott"} = {"boyfriend", "girlfriend", "boycott", "girlcott"}.

(дизъюнкция, чередование) R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.

(замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит ? и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {"Go", "Russia"}* = {?, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}.

Синтаксис

Большинство символов в регулярном выражении представляют сами себя за исключением специальных символов [ ] \ / ^ $ . | ? * + ( ) { }, которые могут быть предварены символом \ (обратная косая черта) («экранированы», «защищены») для представления их самих в качестве символов текста. Можно экранировать целую последовательность символов, заключив её между \Q и \E.

Пример	Соответствие
a\.?	a. или a
a\\\\b	a\\b
a\[F\]	a[F]
\Q+-*/\E	+-*/

Аналогично могут быть представлены другие специальные символы (набор символов, требующих экранирования, может отличаться в зависимости от конкретной реализации). Часть символов, которые в той или иной реализации не требуют экранирования (например, угловые скобки < >), могут быть экранированы из соображений удобочитаемости.

Метасимвол. (точка) означает один любой символ, но в некоторых реализациях исключая символ новой строки.

Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. В частности, [абв]задаёт возможность появления в тексте одного из трёх указанных символов, а [1234567890] задаёт соответствие одной из цифр. Возможно указание диапазонов символов: например, [А-Яа-я] соответствует всем буквам русского алфавита, за исключением букв «Ё» и «ё».