|
Основы компиляции - Лекция 2
Автор: А.Г.Дымченко Материал к лекции 2. Иерархия Хомского. Регулярные языки. Классификация грамматик по сложности соответствующих прогҰ рамм-распознавателей называется иерархией Хомского. В ней выдеҰ лены 4 класса грамматик (в порядке возрастания сложности):
Класс языка определяется классом самой простой (в смысле иерархии Хомского) из описывающих его грамматик. Следующие влоҰ жения для классов языков очевидны, если не рассматривать КС-грамматики, содержащие так называемые e-правила - правила с пустой правой частью. (Упражнение: показать, что любой КС-язык может быть описан грамматикой без e-правил). а < б < в < рекурсивные множества < г = рек.перечислимые мн-ва Для языка, определенного регулярной грамматикой, всегда можҰ но написать контекстно-свободную грамматику (и даже грамматику без ограничений!). Тем не менее, все вложения строгие: в каждом классе существуют языки, которые нельзя задать грамматиками боҰ лее простого класса. Конечные автоматы Рассмотрим другой способ задания регулярных языков. (НедеҰ терминированный) конечный автомат задается:
Принято изображать автомат в виде ориентированного графа, узлы которого соответствуют состояниям (конечные состояния мы будем заключать в двойную рамку), а ребра, помеченные символами входҰ ного алфавита или е, изображают отношение переходов. Цепочка допускается автоматом если и только если существует пусть из начального в одно из конечных состояний, такой что, прочитав метки ребер вдоль этого пути, мы получим исходную цеҰ почку (буква 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
Несложно показать (упражнение), что для каждого автомата можно построить регулярную грамматику, описывающую тот же самый язык, и наоборот. Детерминированный конечный автомат - частный случай недеҰ терминированного, в котором:
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 не является регулярным? - упражҰ
нение.
Задачи и упражнения
- конец материала к лекции 2 - |
Автор проекта: USU Software
Вы можете выкупить этот проект.