Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Материал к лекции 2. Иерархия Хомского. Регулярные языки. Классификация грамматик по сложности соответствующих прог¦ рамм-распознавателей называется иерархией Хомского. В ней выде¦ лены 4 класса грамматик (в порядке возрастания сложности): а) регулярные (или автоматные). Правила имеют вид: A : xB или A : x, где x - цепочка терминалов или e Примеры - упражнение. б) контекстно-свободные (или КС). Правила имеют вид: A : y, где y - цепочка из терминалов и нетерминалов Примеры - "скобочный язык" из предыдущей лекции, язык арифметических формул в) контекстно-зависимые (неукорачивающие). Правила имеют вид : z : y, где z и y - цепочки из терминалов и нетерми¦ налов, z содержит нетерминал, |z| <= |y| n n n Пример: a b c г) без ограничений Класс языка определяется классом самой простой (в смысле иерархии Хомского) из описывающих его грамматик. Следующие вло¦ жения для классов языков очевидны, если не рассматривать КС-грамматики, содержащие так называемые e-правила - правила с пустой правой частью. (Упражнение: показать, что любой КС-язык может быть описан грамматикой без e-правил). а < б < в < рекурсивные множества < г = рек.перечислимые мн-ва Для языка, определенного регулярной грамматикой, всегда мож¦ но написать контекстно-свободную грамматику (и даже грамматику без ограничений!). Тем не менее, все вложения строгие: в каждом классе существуют языки, которые нельзя задать грамматиками бо¦ лее простого класса. Конечные автоматы Рассмотрим другой способ задания регулярных языков. (Неде¦ терминированный) конечный автомат задается: - алфавитом входных символов E; - множеством состояний S; - тернарным отношением переходов на множестве { S, E U e, S }; - начальным состоянием - выделенным состоянием в S, и - конечными состояниями - непустым подмножеством S. Принято изображать автомат в виде ориентированного графа, узлы которого соответствуют состояниям (конечные состояния мы будем заключать в двойную рамку), а ребра, помеченные символами вход¦ ного алфавита или е, изображают отношение переходов. Цепочка допускается автоматом если и только если существует пусть из начального в одно из конечных состояний, такой что, прочитав метки ребер вдоль этого пути, мы получим исходную це¦ почку (буква e, естественно, не читается). Например, автомат --------¬ 0 --------¬ 1 -T-----T¬ ¦ S +-->--+ B +-->--+¦ C ¦¦ L-------- L---T---- L+--T--+- L------<-------0 допускает цепочки (01)+. Этот язык можно описать регулярной грамматикой: S : 0 B B : 1 C C : 0 B C : e Несложно показать (упражнение), что для каждого автомата можно построить регулярную грамматику, описывающую тот же самый язык, и наоборот. Детерминированный конечный автомат - частный случай неде¦ терминированного, в котором: - нет e-переходов, - отношение переходов является однозначной функцией f:( S x E U e ) -> S, определенной, может быть, не для всех пар из SxEUe. В терминах графа это означает, что из одного состояния выходит не более одного ребра с одинаковой меткой. Для детерминированного автомата очень просто проверять при¦ надлежность цепочки из E* языку. Добавив, если нужно, еще одно "тупиковое" состояние, можно сделать функцию переходов опреде¦ ленной на всех парах из S x E. ----T------¬ ¦ ¦ 0 1 ¦ s := начальное состояние +---+------+ цикл для каждого символа цепочки c выполнить ¦ S ¦ B F ¦ . s := f( s, c ) ¦ B ¦ F C ¦ конец цикла ¦ C ¦ B F ¦ ответ := s - конечное состояние ¦ F ¦ F F ¦ L---+------- Такая интерпретация детерминированного конечного автомата более наглядна и общепринята: KA - устройство, которое может находится в конечном множестве состояний и переходит из одного состояния в другоe под действием внешних событий из алфавита E. Можно ли подобным образом интерпретировать недетерминирован¦ ный автомат (или хотя бы эффективно определять принадлежность цепочки языку)? Да, можно считать, что в том случае, когда воз¦ можен более чем один переход, создается необходимое число эк¦ земпляров КА, которые переводятся во все возможные в этой ситу¦ ации состояния. Цепочка считается допущенной, если хотя бы один из экземпляров оказался в конечном состоянии. -<--------------------------¬0 ----+---¬ 0 --------¬ 1 -T--+--T¬ ¦ S +-->--+ B +-->--+¦ C ¦¦ L-------- L---T---- L+--T--+- L<-------------0 Какие цепочки допускает этот автомат? - упражнение. Заметим, что если несколько экземпляров недетерминированного КА оказались в одном состоянии, то в дальнейшем можно рассмат¦ ривать только один из них. Таким образом, максимальное коли¦ чество экземпляров не превосходит числа состояний. Проверить, допускает ли недетерминированный конечный автомат цепочку символов, также несложно: S := e-замыкание( { начальное состояние } ) цикл для каждого символа цепочки c выполнить . S := e-замыкание( F( S, c ) ) конец цикла ответ := ( S П конечные состояния ) - непусто Здесь: S - подмножество множества состояний KA; e-замыкание( S ) - множество состояний, достижимых из S за 0 и более e-переходов; F( S, c ) - множество состояний, достижимых из S за один переход, помеченный символом c. Упражнение по программированию: придумайте структуры данных для представления детерминированного и недетерминированного ко¦ нечных автоматов и запрограммируйте проверку допуска строки из символов ASCII KA. Это можно (и следует) делать за время - O(длина цепочки) для детерминированного и - O(длина цепочки*число состояний) для недетерминированного КА. Преобразование недетерминированного КА в детерминированный Недетерминированный КА всегда можно преобразовать в эквива¦ лентный (т.е. допускающий то же множество цепочек) детерминиро¦ ванный КА. Рассмотрим новый КА, состояниями которого будут под¦ множества множества состояний исходного КА (если исходный авто¦ мат имел m состояний, сколько их будет у нового? - упражнение). Исходным для нового автомата будет состояние {Начало}, конечны¦ ми - все состояния, содержащие исходное конечное состояние. Пе¦ реход A -> B по символу d имеется в новом автомате тогда и только тогда, когда в исходном автомате для любого состояния b из B, существует a из A такое, что по символу d возможен пере¦ ход a -> b, и других переходов по d из A нет. Новый автомат бу¦ дет детерминированным и эквивалентным исходному. Действительно, состояние нового автомата a+b соответствуют размещению экземпляров исходного недетерминированного КА в сос¦ тояниях a и b, а переход в новом автомате соответствует перехо¦ дам всех экземпляров недетерминированного КА. Для практических целей применяется аналогичный алгоритм: На¦ зовем состояния неразличимыми, если в них происходит переход из одного и того же состояния при одном и том же входном символе. Возьмем любое множество неразличимых состояний и добавим в спи¦ сок состояний КА еще одно - их "сумму", перемещая переходы: Было: ¦ Стало: --¬1 --¬0 --¬ ¦ --¬1 ----¬0 ¦ +->+Б+->+В¦ ¦ ¦ +->+Б+Г+>T->¬ ¦А¦ L-- L-- ¦ ¦А¦ L---- ¦ ¦ ¦ ¦1 --¬0 --¬ ¦ ¦ ¦ --¬0 -+¬ ¦ ¦ +->+Г+->+Д¦ ¦ ¦ ¦ ¦Б+->+В¦ ¦ L-- LT- L-- ¦ L-- L-- L-- ¦ --¬1 ¦ ¦ --¬1 --¬0 -+¬ ¦Е+->-- ¦ ¦Е+->+Г+->---+Д¦ L-- ¦ L-- L-- L-- Получим новый (быть может, вновь недетерминированный) КА. Будем повторять наши действия, пока в КА остаются неразличимые состо¦ яния. Этот процесс в конце концов завершится (почему? - упраж¦ нение). При этом мы получим детерминированный автомат, эквива¦ лентный исходному (почему? - упражнение). Применив этот метод к недетерминированному КА из примера в этой лекции, получим: --<----------¬ 1 --------¬ 0 --------¬ 1 -T--+--T¬0 -----+----¬ ¦ S +->--+ B +->--+¦ C ¦+-->+ S + B ¦ L-------- L---T---- L+-----+- L----T----- L--<----------------------- 0 Минимизация конечного автомата По конечному автомату часто можно построить автомат с мень¦ шим числом состояний, эквивалентный исходному. Соответствующий процесс называется минимизацией конечного автомата. Вначале выбросим из автомата все состояния, недостижимые из начального. Затем разобьем все состояния КА на классы эквивалентности сле¦ дующим способом: в первый класс отнесем все конечные состояния, а во второй - все остальные. Назовем эти состояния 0-эквива¦ лентными. Теперь построим новое 1-эквивалентное разбиение, вы¦ делив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния. Последовательно строя n+1-эквива¦ лентные состояния по n-эквивалентным, мы будем увеличивать чис¦ ло классов эквивалентности. Прекратим этот процесс тогда, когда n+1-эквивалентное состояние совпадет с n-эквивалентным. Каждый полученный класс эквивалентности и будет состоянием нового ми¦ нимизированного КА, эквивалентного исходному (почему? - упраж¦ нение). Рассмотрим, например, следующий КА: --------¬1 -T-----T¬ 0--------¬ -------¬0->+ B +->--+¦ D ¦+<-+ F ¦ ¦Начало+-- L-T------ -++---T-+- L---T-T-- ¦ ¦ ¦ --<-----0 -->- ¦1 -->- ¦1 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ L<-+------¬0 ¦1 -<- ¦0 -<- ¦ A +-¬ -----+--¬1 LTT+--+-T¬ 1-+--+---¬ L-------1L>+ C +->--+¦ E ¦¦<-+ G ¦ L-------- L+-----+- L-------- Состояния F и G недостижимы (это можно выяснить, например, вы¦ числив транзитивное замыкание отношения "есть переход"). Пос¦ троим классы n-эквивалентности для оставшихся состояний: n Классы 0 (ABC) (DE) 1 (A) (BC) (DE) 2 (A) (BC) (DE) Результат: ------¬0,1 ------¬1 -T---T¬ ¦ A +---->+ B+C +---->+¦D+E¦¦ L------ L--T--- L+-T-+- L-<----------0 Упражнение: докажите, что для любого КА существует и единственен с точностью до изоморфизма минимальный эквива¦ лентный ему конечный автомат. Покажите, что описанный выше ал¦ горитм минимизации получает на выходе минимальный автомат. Упражнение по программированию: придумайте структуры данных и запрограммируйте процедуры построения детерминированного КА, и минимизации КА. Какая временная и пространственная сложность предложенных вами алгоритмов в терминах числа состояний исход¦ ного и выходного автоматов? Регулярные языки и регулярные выражения Рассмотрим специальный класс операций над языками - регуляр¦ ные операции, множество языков, получаемое в результате приме¦ нения конечного числа регулярных операций из элементарных язы¦ ков, - регулярные множества, способ их описания - регулярные выражения и недетерминированные конечные автоматы, допускающие цепочки из этих множеств. ---------------------T-----------T----------------------------¬ ¦ Регулярное ¦Регулярное ¦ Конечный автомат ¦ ¦ множество ¦ выражение ¦ ¦ +--------------------+-----------+----------------------------+ ¦ Пустая цепочка ¦ e ¦ ------¬ e -T---T¬ ¦ ¦ ¦ ¦ ¦ S +--->---+¦ E ¦¦ ¦ ¦ ¦ ¦ L------ L+---+- ¦ +--------------------+-----------+----------------------------+ ¦ Один символ a из E ¦ a ¦ ------¬ а -T---T¬ ¦ ¦ ¦ ¦ ¦ S +--->---+¦ E ¦¦ ¦ ¦ ¦ ¦ L------ L+---+- ¦ +--------------------+-----------+----------------------------+ ¦ ¦ ¦ ----¬ e --T-----T-¬ e -T-T¬¦ ¦ P U Q ¦ p|q ¦ ¦ +->-+s¦Авт.P¦e+->-+¦ ¦¦¦ ¦ ¦ ¦ ¦ S ¦ L-+-----+-- ¦¦E¦¦¦ ¦ ¦ ¦ ¦ ¦ e --T-----T-¬ e ¦¦ ¦¦¦ ¦ ¦ ¦ ¦ +->-+s¦Авт.Q¦e+->-+¦ ¦¦¦ ¦ ¦ ¦ L---- L-+-----+-- L+-+-¦ +--------------------+-----------+----------------------------+ ¦ PQ (конкатенация) ¦ pq ¦ ----T-----T----T-----TT-T¬ ¦ ¦ ¦ ¦ ¦ S ¦Авт.P¦ es ¦Авт.Q¦¦Е¦¦ ¦ ¦ ¦ ¦ L---+-----+----+-----++-+- ¦ +--------------------+-----------+----------------------------+ ¦ P* (итерация) ¦ p* ¦ ---<----¬e ¦ ¦ ¦ ¦ ----¬ e -+T-----T+¬ e -T-T¬¦ ¦ ¦ ¦ ¦ S +->-+s¦Авт.P¦e+->-+¦E¦¦¦ ¦ ¦ ¦ L-T-- L-+-----+-- L+T+-¦ ¦ ¦ ¦ eL---------->----------- ¦ +--------------------+-----------+----------------------------+ ¦ P (просто скобки)¦ (p) ¦ ------T-------TT---T¬ ¦ ¦ ¦ ¦ ¦ S ¦ Авт.P ¦¦ E ¦¦ ¦ ¦ ¦ ¦ L-----+-------++---+- ¦ L--------------------+-----------+----------------------------- В регулярном выражении "*" имеет больший приоритет, чем кон¦ катенация, а конкатенация - больший чем "|". Примеры регулярных выражений: (0|1)*, (0|1)(0|1)*. Какие множества они описывают? Для регулярного выражения предложен способ построения неде¦ терминированного конечного автомата, допускающего соответству¦ ющее выражению регулярное множество. Предложенная конструкция не является самой экономной (автомат обычно содержит много "лишних" e-переходов), однако построенный автомат обладает следующими полезными свойствами: - у него только одно конечное состояние, - в начальное состояние не входит ни одно ребро, - из конечного состояния не выходит ни одно ребро. Таким образом, мы доказали, что регулярные множества < регу¦ лярные языки = языки, допускаемые КА. Покажем, что допускаемое КА множество - регулярно. (Это утверждение называется теоремой Клини). Доказательство: Пусть S1,...Sn - состояния детерминированно¦ го КА, S1 - начальное состояние. Рассмотрим все пути в графе переходов с началов в Si, концом в Sj, промежуточными узлами из множества {S1...Sk} (1<=i<=n, 1<=j<=n, 0<=k<=n) и множества це¦ почек из E - L(i,j,k), соответствующие этим путям. Докажем ин¦ дукцией по k, что множества L - регулярны. L(i,j,0) - состоит из меток ребер, ведущих из Si в Sj, сле¦ довательно, регулярно. Для 0<=k<=n-1 L(i,j,k+1) = L(i,j,k) U L(i,k+1,k) L(k+1,k+1,k)* L(k+1,j,k) получено с помощью регулярных операций из регулярных мно¦ жеств, следовательно, регулярно. Множество цепочек, допускаемых КА, представляет собой объеди¦ нение цепочек L(1,j,n), таких, что Sj - конечное состояние КА, следовательно, регулярно. (Конец доказательства). Мы рассмотрели 4 способа описания языков: - регулярные (автоматные, праволинейные) грамматики, - недетерминированные КА, - детерминированные КА, - регулярные выражения, и показали, что они описывают один класс языков - регулярные языки. Этот класс языков "устроен очень хорошо" - для всех ти¦ пичных вопросов известны ответы и эффективные алгоритмы. Приме¦ ры таких вопросов (получение ответов - упражнение): - является ли объединение, пересечение, дополнение регулярных языков регулярным, - является ли регулярный язык конечным, пустым, - совпадают ли два регулярных языка, - является ли один регулярный язык подмножеством другого, и т.д. (Замечание. Для других классов иерархии Хомского дела обстоят значительно хуже, например, проблема эквивалентности для КС-языков алгоритмически неразрешима.) Лемма о разрастании для регулярных языков Так называмые "леммы о разрастании" для классов языков - удобный способ доказательства того, что конкретный язык не от¦ носится к данному классу. Лемма для регулярного языка: Существует такое число m, что любую цепочку x, |x| > m, принадлежащую языку, можно разбить на три части: x = uvw так, что 0<|v|<=m и цепочки uv*w также будут принадлежать языку. Доказательство: построим КА для распознава¦ ния языка. Пусть этот автомат имеет m состояний. Тогда при раз¦ боре цепочки x хотя бы одно из состояний (например, А) прохо¦ дится дважды (почему? - упражнение). Разобьем цепочку x на три части - до состояния А, от А до А, остальное. Это и есть цепоч¦ ки u,v,w (почему v можно размножать, сохраняя принадлежность цепочки языку? - упражнение). n n Как показать, что язык 0 1 не является регулярным? - упраж¦ нение. Задачи и упражнения 1. Написать регулярную грамматику и регулярное выражение, порождающие тот же язык, что и грамматика: S : AB ; A : X|Y ; X : x|xX ; Y : y|yY ; B : b|bB 2. Построить регулярную грамматику и конечный автомат, соот¦ ветствующие регулярному выражению: (101)*(010)* 3. Постройте недетерминированный а затем детерминированный конечные автоматы, воспринимающие регулярное выражение: (101)*(110)* 4. Построить детерминированные конечные автоматы для следу¦ ющих регулярных выражений. Для каждого полученного автомата построить эквивалентный минимальный автомат. Убедиться в изо¦ морфизме минимальных автоматов, следовательно, в эквивалентнос¦ ти исходных выражений: (a|b)* (a*|b*)* ((e|a)b*)* 5. Написать регулярное выражение, описывающее следующий язык - слово, буквы которого расположены в алфавитном порядке - последовательность цифр, в которой нет повторяющихся цифр - последовательность цифр, в которой не более чем одна цифра встречается несколько раз - строка из нулей и единиц, в которой нет подстроки 0 0 1 - строка из нулей и единиц, в которой нет подпоследователь¦ ности 0 0 1 6. Опишите регулярной грамматикой и приведите регулярное вы¦ ражение для идентификатора Фортрана. (До шести букв или цифр, первый символ должен быть буквой). 7. Напишите программу распознавания вещественных констант. Она должна воспринимать константы вида: 1.2 -0.4 +3.14 .2 1. -1.е38 1е+2 +0.5е-23 и т.д. 8. Построить минимальные детерминированные конечные автоматы для следующих регулярных выражений (a|b)*a(a|b) (a|b)*a(a|b)(a|b) (a|b)*a(a|b)(a|b)(a|b) Доказать, что любой детерминированный конечный автомат для вы¦ ражения (a|b)a(a|b)(a|b)...(a|b), содержащего n-1 (a|b) в конце содержит не менее чем 2**n состояний. 9. Напишите программу, которая проверяет, является ли имя файла частным случаем разновидности регулярного выражения, в котором метасимвол * обозначает любую (в том числе и пустую) последовательность символов кроме ".", а метасимвол ? - любой символ кроме "." - конец материала к лекции 2 -