Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 42
Текст из файла (страница 42)
Минииизаиия детерминированных конечных автоматов. Состояния любого ДКА можно разбить на группы взаимно неразличимых состояний. Состояния из двух разных групп всегда различимы. Если заменить каждую группу одним состояни- ем, получим эквивалентный ДКА с наименьшим числом состояний. Литература За исключение объединения, кон РЕЗЮМЕ 183 м очевидных свойств замкнутости регулярных выражений (относительно катенации и итерации), ко~орые были доказаны Клини [б), почти все результаты свойств замкнутости воспроизводят аналогичные результаты, полученные для контекстно-свободных языков (этому классу языков посвящены следующие главы). Таким образом, лемма о накачке для регулярных языков является упрощением соответствующего результата для контекстно-свободных языков (Бар-Хиллел, Перлес и Шамир [1)).
Из результатов этой работы следуют некоторые другие свойства замкнутости, представленные в данной главе, а замкнутость относительно обратного гомоморфизма обоснована в [2). Операция деления (см. упражнение 4.2.2) представлена в [3]. В этой работе обсуждается более общая операция, в которой вместо одиночных символов находятся регулярные языки. Ряд операций "частичного удаления", начиная с упражнения 4.2.8, в котором говорилось о первых половинах цепочек регулярного языка, бьш определен в [8[, Сейферас и Мак-Нотон [9) изучили общий случай, когда операция удаления сохраняет регулярность языков.
Алгоритмы разрешения, такие как проверка пустоты и конечности регулярных языков, а также проверка принадлежности к регулярному языку, берут свое начало в [7). Алгоритмы минимизации числа состояний ДКА появились в [5[. В работе [4) предложен наиболее эффективный алгоритм нахождения минимального ДКА. 1. У. Ваг-Нй!е1, М. Рег!ек, апг! Е. ЕЬапнг, "Оп Гоппа! ргорепйек оГйпр!е рЬгаке-кггисшге 8гагпшагк," с. РйопеглЬ Брасйгг!кк.
КоттипГГгаггопк-ГогксГг. 14 (1961), рр. 143-172. 2. 5. б!пкЬиг8 апг! б. Коке, "Орегайопк тгЬ!сЬ ргекегте дебпаЬ!!!гу !и!ап8иа8ек,".1 АСМ 10:2 (1963), рр. 175-195. (Гинзбург С., Роуз Дж. Об инвариантности классов языков относительно некоторых преобразований. — Кибернетический сборник, Новая серия, вып. 5. — Мл Мир, 1968. — С. 138 — 166.) 3.
5.бшкЬиг8 апг! Е.Н.Зрап!ег, "Оио!!еп!к оГ сопгехг-Ггее !апйиайек,'*,7. АСМ 10:4 (1963), рр. 487-492. 4. 3. Е. НорсгоГг, "Ап п !о8 п а!ЕоП1Ьгп Гог ш!и!ш!х!п8 Гье к!а!ел !и а Вийе аигопзагоп,'* !и 2, КоЬаьй (еб.) Тйе ТГгеогу оГМас)г!пек апсГ Сотригаггопг, Асаг!ет!с Ргекк, Ыезт Уог!г, рр. 189 — 196. (ХопкрофтДж. Алгоритм для минимизации конечного автомата.— Кибернетический сборник, Новая серия, вып. 11. — Мл Мир, 1974. — С. 177 — ! 84.) 5.
1). А. НиГбпап, "ТЬе купгЬекВ оГ кеоиепг!а! кзг!гсЫп8 сиси!гк,",У. РгапГ21п Гпкг. 257:3-4 (! 954), рр. 161 — 190 апг) 275 — 303. 6. 8. С. К!еепе, "Кергекепгайоп оГ ечеп!к !и легче пе!к апо Вийе аигогпага," !и С. Е. 8Ьаппоп апов), МсСаггЬу, Аиготага 5гиабвк, РНпсегоп Бппс Ргекк, 1956, рр. 3 — 42. (Клини С.К. Представление событий в нервных сетях. — сб. "Автоматы*'.— Мл ИЛ, 1956.
— С. 15-67.) 7. Е. Г. Мооге, "бедап1геп ехрегцпепгк оп кециев!!а! гпасЬ!пек," !и С. Е. ЕЬаппоп апг! 1. МсСаг!Ьу, 4иготага 5гньбел РНпсегоп !)шж Ргекк, 1956, рр. 129 — 153. (Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами. — сб. "Авгпоматы". — Мл ИЛ,!956.
— С.!79 — 210.) 8. К. Е. 5!еагпк апг( 1. Нагвпап!к, "Кейп!аг!Гу-ргекегт!п8 шог!!Ггса!!опк оГ гейи!аг ехргекк!опк," ГпГагтаг!оп апгГ Сап!го! 6; 1 (1963), рр. 55-69. 9. 1.1. Бе!Гегак апг! Р. МсНаи8Ь!оп, "Ке8и!аг!гу-ргекегч!п8 шог!!Всаг!опк," Тдеагеггса! Сотригег 5с!енсе 2:2 (1976), рр. 147 — 154. 184 ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ ГЛАВА 5 Контекстно-свободные грамматики и языки Перейдем от рассмотрения регулярных языков к более широкому классу языков, которые вазываются контекстно-свободными.
Они имеют естественное рекурсивное описание в виде контекстно-свободных грамматик. Эти грамматики играют главную роль в технологии компиляции с начала 1960-х годов; они превратили непростую задачу реаяизации синтаксических аначизаторов, распознающих структуру программы, из неформальной в рутинвую, которую можно решить за один вечер. Позже коигексгно-свободные грамматики стали использоваться двя описания форматов документов в виде так называемых определений типа документов (досшпепьгуре дегппгюп — 1)тО), которые применяются в языке хме (ех1евз1Ые шагкпр!андраде) для обмена информацией в 1пгегпег. В этой главе определяется система записи контекстно-свободных грамматик и показывается, каким образом они определяют языки.
Обсуждается понятие дерева разбора, июбражающего структуру, которую грамматика налагает на цепочки языка. Дерево разбора представляет собой выход синтаксического анализатора языка программирования и одновременно общепринятый способ выражения структуры программы. Контекстно-свободные языки также описываются с помощью магазинных автоматов, рассматриваемых в главе б. Эти автоматы не столь важны, как конечные, однако в качестве средства определения языков они эквиваяентны контекстно-свободным грамматикам и особенно полезны при изучении свойств замкнутости и разрешимости контекстно- свободных языков (глава 7).
5.1. Контекстно-свободные грамматики Начнем с неформального представления контекстно-свободных грамматик, затем рассмотрим их некоторые важные свойства. Далее определим их формально и предста- вим процесс "вывода", с помощью которого грамматика задает цепочки языка. 5.1.1. Неформальный пример Рассмотрим язык паяиндромов. Патипдрои — это цепочка, читаемая одинаково слева направо и наоборот, например, о Го или пас1атзшас1агв ("Мадаш, Рт Лдаш" — по преданию, первая фраза, услышанная Евой в Райском саду), Другими словами, цепочка гг является паяиндромом тогда и только тогда, когда и = в .
Дпя упрогцения рассмотрим описание палиндромов только в алфавите !О, 1). Этот язык включает цепочки вроде 0110, 11011, к, но не включает 011 нли 0101. Нетрудно проверить, что язык б ~ палиндромов из символов 0 и 1 не является регулярным. Используем для э~ого лемму о накачке. Если язык 1 ~ регулярен, то пусть ив соответствующая константа из леммы.
Рассмотрим палиндром н = 0" 10". Если б ~ регулярен, то н можно разбить на н = ху- так, что у состоит из одного или нескольких нулей из их первой группы. Тогда в слове хх, которое также должно быть в Ее,ь если Е, ~ регулярен, слева от единицы будет меньше нулей, чем справа. Следовательно, хх не может быть палиндромом, что противоречит предположению о регулярности б н Существуе~ следующее естественное рекурсивное определение того, что цепочка из символов 0 н 1 принадлежит языку б н Оно начинается с базиса, утверждающего, что несколько очевидных цепочек принадлежат Е н а затем использует идею того, что если цепочка является палиндромом, то она должна начинаться и заканчиваться одним и тем же символом.
Кроме того, после удаления первого и последнего символа остаток цепочки также должен быть палиндромом. Базис. к, 0 и 1 являются палиндромами. Индукция. Если зо — палиндром, то ОнО н 1зе! — также палиндромы. Ни одна цепочка не является палиндромом, если не определяется этими базисом и индукцией. Контекстно-свободная грамматика представляет собой формальную запись подобных рекурсивных определений языков. Грамматика состоит из одной или нескольких переменных, которые представляют классы цепочек, или языки.
В данном примере нужна только одна переменная, представляющая множество палиндромов, т.е. класс цепочек, образующих язык Уе, Имеются правила построения цепочек каждого класса. При построении используются символы алфавита и уке построенные цепочки из различных классов. Пример 5.1. Правила определения палиндромов, выраженные в виде контекстно-свободной грамматики, представлены на рис. 5.1. В разделе 5.1.2 мы рассмотрим их подробнее.
Первые три правила образуют базис. Они говорят, что класс палиндромов включает цепочки к, 0 н 1. Эти правила образуют базис, поскольку ни одна из их правых частей (справа от стрелок) не содержит переменных. Последние два правила образуют индуктивную чань определения.
Например, правило 4 гласит, что если взять произвольную цепочку н из класса Р, то ОмО также будет в классе Р. Аналогично, по правилу 5 цепочка 1и1 также будет в классе Р. П 1. Р— зк 2. Р— эО 3. Р— >1 4. Р— + ОРО 5. Р -о 1Р! Рис 5 А Контекстно-свободная грамматика дяя наяиндромоа 186 ГЛАВА 6.
КОНТЕКСГНО-СВОВОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 5.1.2. Определение контекстно-свободных грамматик Описание языка с помощью грамматики состоит из следуюгдих четырех важных компонентов. 1. Есть конечное множество символов, из которых состоят цепочки определяемого языка. В примере о пачиндромах это было множество (О, 1). Его символы называ- ются терминальными, или гнерминалами. 2. Существует конечное множество переменных, называемых иногда также нетерминатаии, или синмаксичесними категориями. Каждая переменная представляет язык, т.е.
множество цепочек. В рассмотренном примере была только одна переменная, Р, которая использовалась лля представления класса палиндромов в алфавите (О, ) ). 3. Одна из переменных представляе~ определяемый язык; она называется сгнартоеым символом. Другие переменные представляют дополнительные классы цепочек, которые помогают определить язык, заданный стартовым символом. 4. Имеется конечное множество продукций, или правил оыаода, которые представляют рекурсивное определение языка. Каждая продукция состоит из следующих частей: а) переменная, (частично) определяемая продукцией. Эта переменная часто называется головой продукции; б) символ продукции — ~; в) конечная цепочка, состоящая из терминалов и переменных, возможно, пустая.
Она называется телам продукции и представляет сгюсоб образования цепочек языка, обозначаемого переменной в голове. По этому способу мы оставляем терминалы неизменными и вместо каждой переменной в теле подставляем любую цепочку, про которую известно, что она принадлежит языку этой переменной. Пример множества продукций приведен на рис. 5.1. Описанные четыре компонента образуют контексано-свободную граммаьчилу, или КС-грамматику, или просто граммаьчилу, или КСГ. Мы будем представлять КС- грамматику О ее четырьмя компонентами в виде О.=- (Г, Т, Р, 5), где à — множес~во переменных, Т вЂ” терминалов, Р— множество продукций, 5 — стартовый символ. Пример 5.2. Грамматика б, ~ для палиндромов имеет вид а...=-((Р), (О,1), А, Р), где А обозначает множество из пяти продукций (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
