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

0	1
->А	В	Е
В	С	F
*С	D	Н
D	Е	Н
Е	F	I
*р	G	В
G	Н	В
Н	I	С
*1	А	Е

Рис. 4.15. Еще один ДКА, который нужно минимизировать

4.4.3. (!!) Пусть р и q — пара различимых состояний заданного ДКА А с п состояния­ми. Какой может быть самая точная верхняя граница длины кратчайшей цепоч­ки, различающей р и q, как функция от п?

Резюме

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

Литература

За исключением очевидных свойств замкнутости регулярных выражений (относительно объединения, конкатенации и итерации), которые были доказаны Клини [6], почти все ре­зультаты свойств замкнутости воспроизводят аналогичные результаты, полученные для контекстно-свободных языков (этому классу языков посвящены следующие главы). Таким образом, лемма о накачке для регулярных языков является упрощением соответствующего результата для контекстно-свободных языков (Бар-Хиллел, Перлес и Шамир [1]). Из ре­зультатов этой работы следуют некоторые другие свойства замкнутости, представленные в данной главе, а замкнутость относительно обратного гомоморфизма обоснована в [2].

Операция деления (см. упражнение 4.2.2) представлена в [3]. В этой работе обсуждается более общая операция, в которой вместо одиночных символов находятся регулярные языки. Ряд операций "частичного удаления", начиная с упражнения 4.2.8, в котором говорилось о первых половинах цепочек регулярного языка, был определен в [8]. Сейферас и Мак-Нотон [9] изучили общий случай, когда операция удаления сохраняет регулярность языков.

Алгоритмы разрешения, такие как проверка пустоты и конечности регулярных язы­ков, а также проверка принадлежности к регулярному языку, берут свое начало в [7]. Ал­горитмы минимизации числа состояний ДКА появились в [5]. В работе [4] предложен наиболее эффективный алгоритм нахождения минимального ДКА.

Y. Bar-Hillel, М. Perles, and Е. Shamir, "On formal properties of simple phrase-structure grammars," Z Phonetik. Spachwiss. Kommunikations-forsch. 14 (1961), pp. 143-172. S. Ginsburg and G. Rose, "Operations which preserve definability in languages," J. ACM 10:2 (1963), pp. 175-195. ( Роуз Дж. Об инвариантности классов языков относительно некоторых преобразований. — Кибернетический сборник, Новая се­рия, вып. 5. — М.: Мир, 1968. — С. 138-166.) S. Ginsburg and Е. Н. Spanier, "Quotients of context-free languages," J. ACM 10:4 (1963), pp. 487-492. J. E. Hopcroft, "An n log n algorithm for minimizing the states in a finite automaton," in Z. Kohavi (ed.) The Theory of Machines and Computations, Academic Press, New York, pp. 189-196. (ХопкрофтДж. Алгоритм для минимизации конечного автомата.— Кибернетический сборник, Новая серия, вып. 11. — М.: Мир, 1974. — С. 177-184.) D. A. Huffman, "The synthesis of sequential switching circuits," J. Franklin Inst. 257:3-4 (1954), pp. 161-190 and 275-303. S. C. 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.) Е. F. Moore, "Gedanken experiments on sequential machines," in С. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp. 129-153. ( Умозрительные эксперименты с последовательностными машинами. — сб. "Авто­маты".— М.: ИЛ, 1956, —С. 179-210.) R. Е. Stearns and J. Hartmanis, "Regularity-preserving modifications of regular expressions," Information and Control 6:1 (1963), pp. 55-69. J. I. Seiferas and R. McNaughton, "Regularity-preserving modifications," Theoretical Computer Science 2:2 (1976), pp. 147-154.

ГЛАВА 5

Контекстно-свободные

грамматики и языки

Перейдем от рассмотрения регулярных языков к более широкому классу языков, которые называются контекстно-свободными. Они имеют естественное рекурсивное описание в ви­де контекстно-свободных грамматик. Эти грамматики играют главную роль в технологии компиляции с начала 1960-х годов; они превратили непростую задачу реализации синтак­сических анализаторов, распознающих структуру программы, из неформальной в рутин­ную, которую можно решить за один вечер. Позже контекстно-свободные грамматики ста­ли использоваться для описания форматов документов в виде так называемых определений типа документов (document-type definition — DTD), которые применяются в языке XML (extensible markup language) для обмена информацией в Internet.

В этой главе определяется система записи контекстно-свободных грамматик и пока­зывается, каким образом они определяют языки. Обсуждается понятие дерева разбора, изображающего структуру, которую грамматика налагает на цепочки языка. Дерево раз­бора представляет собой выход синтаксического анализатора языка программирования и одновременно общепринятый способ выражения структуры программы.

Контекстно-свободные языки также описываются с помощью магазинных автоматов, рассматриваемых в главе 6. Эти автоматы не столь важны, как конечные, однако в каче­стве средства определения языков они эквивалентны контекстно-свободным граммати­кам и особенно полезны при изучении свойств замкнутости и разрешимости контекстно - свободных языков (глава 7).

5.1. Контекстно-свободные грамматики

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

5.1.1. Неформальный пример

Рассмотрим язык палиндромов. Палиндром — это цепочка, читаемая одинаково слева направо и наоборот, например, otto или madamimadam ("Madam, I'm Adam" — по пре­данию, первая фраза, услышанная Евой в Райском саду). Другими словами, цепочка w является палиндромом тогда и только тогда, когда w = мЛ Для упрощения рассмотрим описание палиндромов только в алфавите {0, 1}. Этот язык включает цепочки вроде 0110, 11011, е, но не включаетОП или0101.

Нетрудно проверить, что язык Lpa/ палиндромов из символов 0 и 1 не является регу­лярным. Используем для этого лемму о накачке. Если язык Lpat регулярен, то пусть п — соответствующая константа из леммы. Рассмотрим палиндром w = 0П10". Если Lpa/ регу­лярен, то w можно разбить на w = xyz так, что у состоит из одного или нескольких нулей из их первой группы. Тогда в слове xz, которое также должно быть в Lpai, если Lpai регу­лярен, слева от единицы будет меньше нулей, чем справа. Следовательно, xz не может быть палиндромом, что противоречит предположению о регулярности Lpa/.

Существует следующее естественное рекурсивное определение того, что цепочка из символов 0 и 1 принадлежит языку Lpa/. Оно начинается с базиса, утверждающего, что несколько очевидных цепочек принадлежат Lpah а затем использует идею того, что если цепочка является палиндромом, то она должна начинаться и заканчиваться одним и тем же символом. Кроме того, после удаления первого и последнего символа остаток цепоч­ки также должен быть палиндромом.

Базис, е, 0 и 1 являются палиндромами.

Индукция. Если w— палиндром, то OwO и 1 w 1 — также палиндромы. Ни одна це­почка не является палиндромом, если не определяется этими базисом и индукцией.

Контекстно-свободная грамматика представляет собой формальную запись подобных рекурсивных определений языков. Грамматика состоит из одной или нескольких перемен­ных, которые представляют классы цепочек, или языки. В данном примере нужна только одна переменная, представляющая множество палиндромов, т. е. класс цепочек, образую­щих язык Lpai. Имеются правила построения цепочек каждого класса. При построении ис­пользуются символы алфавита и уже построенные цепочки из различных классов.