Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 31
Текст из файла (страница 31)
Приведем алгоритм, описывающий процесс минимизации числа состояний конечного автомата. А л г о р и т м 2.2. П о с т р о е н и е к а н о н и ч е с к о г о к о п е чного автомата. Вход. Конечный автомат М = (!с, Х, 6, д„г). Выход. Эквивалентный приведенный кайечиый автомат М'. !АТ Гл. а. элементы теОРии яэыкОВ Тевлина 2.В [А] [В] [С[ [А] [В[ [С] [В] [С] [А] Рас.
2.7. Дваграмма автомата М. 151 150 Метод. Шаг 1: Применив к диаграмме автомата М алгоритм 0.3, найти состояния, недостижимые из цв. Устранить все недости- жимые состояния. Шаг 2: Строить отношения эквивалентности ==', = — ', ..., как описано в лемме 2.11, да тех пор, пока два из них не совпадут: ==а" ===а. Взять в качестве = =отношение .==". Шаг 3: Построить конечный автомат М' = (]Е', г., 6', д„', Р'), где (а) ]]' †множест классов эквивалентности отношения (обозначим через [р1 класс эквивалентности отношения = †-, со- держащий состояние р), (6) 6' ((р), а) = ) а1, если 6 (р, а) = д, (в) аа' — это (да), (г? р'=((уийр).
П Можно непосредственно показать, что шаг 3(б) непротиворе- чие, т. е. какой элемент класса (р] ни взять, для 6((р1, а) бу- дет один н тот же класс. Доказательство равенства Е (М) --Е (М') тоже просто и оставляется в качестве упражнения. Докажем теперь, что автомат с меньшим числом состояний, чем у М', не может допускать Е(М). Теорема 2.6. Автомат М', который строится алгоригпмом 2.2, имеет наименыиее число состояний среди всех конечных ав- томатов, даггуекающих язык Е (М). Доказательство.
Предположим, чта М" имеет меныпе состояний, чем М', и что Е(Л[") =Е(М). В силу шага 1 алго- ритма 2.2 каждое состояние автомата М' достижимо. Так как М" имеет меньше состояний, то найдутся цепочки гв и х, переводящие состояние д,' в разные состояния, а д", (начальное состояние автомата М")---в одно и то же: (да, гв) ]- -'м„(Ч, е) и (и, х) ) — м. (а, е). Следовательно, гв и х переводят автомат М в раз- а.а. сВОйстВА Регмлямных мнОжестВ личимые состояния, скажем р и г.
Зто значит, что существует такая цепочка у, что точно одна из цепочек юу и ху принадлежит Е(М). На юу и ху должны переводить М" в одно и та же состояние з, для которого (у,у) с-м. (З,е). Таким образом,.точно одна из цепочек гву и ху нс может принадлежать Е(М"), а это противоречит предположению а том, что Е(М") в Е(М). Пример 2.16. Найдем приведенный конечный автомат, эквивалентный автомату М, диаграмма которого показана на рис, 2.7. Отношения ==" для й -0 имеют следующие классы эквивалентности: Классы отношения =--'. (А,Г), (В,С,В,Е) Классы отношения ==-': (А, г'), (В, Е), (С, О) Классы отношения ='-: (А, г"), (В, Е), (С, е]) Так как ='==, то = — ===-', Приведенным автоматом М'будет автомат (((А], (В[, [С)), (а,у), 6', А, ([АЦ), где функция 6' определяется табл.
2.3. Здесь мы выбрали (А) для представления класса (А,Р), [В) — для представления (В, Е) и (С) — для (С О). И 2.3.2. Лемма о разрастании для регулярных множеств Теперь мы хотим получить характеристику регулярных множеств, которая будет полезна для доказательства того, что некоторые языки не явля1отся регулярными.
Следующую теорему назовем леммой о „разрастании", потому что ана в сущности говорит о том, что если даны регулярное множество и достаточно длинная цепочка в нем, то в этой цепочке можно найти непустую надцепочку, которую можно повторить сколько угодна раз (т. е, она „,разрастается"), и все полученные таким образом „новые" цепочки будут принадлежать тому же регулярному множеству. С помощью этой леммы часто приводят к противоречию предположение о том, чта некоторое множество регулярно. ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Теорема 2.7, Лемма о разрастании для регулярных множеств.
Пусть  — регулярное множество. Существует такая константа р, что если юб(. и )т)> р, то цепочку 2е можно записать в виде хуг„где 0 <1у((р и ху'гЕВ для всех 2> О. Доказательство. Пусть М=(1е,а,б,д„Р) — конечный автомат с п состояниями и Е (М) = 1.. Пусть р = п. Если ю Е Ь и (ю~ ~ п, рассмотрим последовательность конфигураций, которую проходит автомат М, допуская цепочку ик Так как в этой последовательности по крайней мере и+ 1 конфигураций, то среди первых пл-1 конфигураций найдутся две с одинаковыми состояниями.
Поэтому должна быть такая последовательность тактов, что (уь|Хуг) ) — * (О„уг) ) — 2 (О„г) ( — ' (О„Е) для некоторого д, и 0<й~п. Отсюда 0((у((п. Но тогда для любого 1> 0 автомат может проделать последовательность тактов Хугг) Г л (у угг) (ч у '.г) 1 — + (ро уг) )-' (оо г) ) — ' (д„е) Так как цепочка 2о= хуг принадлежит Ь, то и ху'г6 Е для всех 1>1. Случай 1=0 исследуется аналогично. () Пример 2.16. С помощью леммы о разрастании докажем, что язык Ь = (О" 1" ~ п =. 1) не является регулярным множеством.
Допустим, что Е регулярен. Тогда для достаточно большого и цепочку 0"1' можно записать в виде хуг, причем у~е и ху'гЕТ, для всех 1>0. Если уЕО~ или у~1+, то хг=-ху'ЕТАЯ. Если у Е 0+ 1 ~, то хууг( 1.. Полученное противоречие доказывает, что язык Т. Ие может быть регулярным. () 2.3З. Свойстве замкнутости регулярных множеств Множество А называется замкнутым относительно и-местной операции 9, если 0(а„а„.. „а,)ЕА всегда, когда а;6А для всех 1 ( 2'е- п.
Например, множество целых чисел замкнуто , относительно операции сложения. 2,3. СВОЙСТВА РЕГУЛЯРНЫХ МНОЖЕСТВ В этом разделе мы рассмотрим несколько операций, относительно которых класс регулярных множеств замкнут. С помощью этих свойств замкнутости можно будет определить, регулярны ли некоторые языки. Мы уже знаем, что если Е, и 1.„— регулярные множества, то множества 1,,(11,„1.,62 и 1.; тоже регулярны. Определение. Класс множеств называется булевой алгеброй множеств, если он замкнут относительно объединения, пересечения н дополнения. Теорема 2.6. Для любого алфавита г. класс регулярных множеств, содержащихся в Х', является булевой алгеброй множеств.
До к а з а тел ь ст в о. Докажем замкнутость относительно дополнения, Замкнутость относительно объединения мы уже имеем, а замкнутость относительно пересечения будет следовать из теоретико-множественного закона А () В= А (1 В (упр.
0.1А). Пусть М = ((е, Ь, 6, д„Р) — конечный автомат, у которого Ь ~ Т.. Легко показать, что каждое регулярное множество Ь =Х" допускается некоторым таким автоматом. Тогда конечный автомат М' = (О, Ь, 6, д„(с — г") допускает Ь* — й (М). Заметим, что здесь использован тот факт, что автомат М полностью определен. Далее, дополнение ~(М) относительно 2* можно представить в виде В (М) =Ь (М ') О г" (2 — Ь) а*.
Так как множество 2* (Š— Ь) Х* регулярно, то регулярность множества (. (М) следует нз замкнутости регулярных множеств относительно объединения, С) Теорема 2.9. Класс регулярных множеств замкнут относительно обращения. Доказательство. Пусть М=((), л', 6, о„Р) — конечный автомат, определяющий регулярное множество Ь. Чтобы определить ЬЯ, „запустим М в обратном направлении". Иными словами, возьмем недетерминированный конечный автомат М'= ((г О (д'.), Е, 6', ц;, г'), где Р'=(д,), если е((., и г'=(д„д',), если ебЬ, Функцию 6' определим так: (1) 6'(дь', а) содержит д, если 6(д, а) Ер. (2) 6' (д', а) для всех д' Е (г и а Е л содержит у, если 6 (д, а) =-,у'.
Легко показать, что (д„ю)-) — м (о, е) для о ~г тогда и только тогда, когда (у,', 2ея) ( — м, (у„е). таким образом, ь (м') (Ь (М))" 1,Я. Класс регулярных множеств замкнут относительно самых распространенных операций над языками. Многие из этих свойств замкнутости изучаются в упражнениях. ГЛ. Е. ЭЛЕМЕНТЫ ТЕОРИЙ ЯЗЫКОВ ЗЛ СВОЙСТВА РЕГУЛЯРНЫХ МНОЖЕСТВ 2.3.4.
Рвзрвшммые проблемы, связанные с регулярными множествами Мы изложили несколько способов опнсания регулярных множеств, таких, как регулярные выражения и конечные автоматы. В связи с этими способами представления языков естественно возникают алгоритмические проблемы. Мы коснемся здесь трех проблем: Проблема принадлежности:,Даны определенного типа описание языка и цепочка ш; принадлежит лн Ги этому языку?" Проблема пустота:,Дано определенного типа Описание языка; пуст лн этот языку" Проблел4и эквивалентности:,Даны два Описания одинакового типа; определяют ли они один и тот же язык?" Мы рассмотрим следующие типы описанйй регулярных множеств: (1) регулярные выражения, (2) праволииейные грамматики, (3) конечные автоматы. Сначала дадим алгоритмы, решающие три упомянутые выше проблемы в том случае, когда языки описываются с помощью конечных автоматов. Алгоритм 2.3. Решение проблемы принадлежностин для конечных автоматов, Вход.
Конечный автомат М = Я, Х, 6, д„Р) и цепочка ю ЕЕ*. Выход.,ДА", если юЕТ, (М); „НЕТ", если ю!ГТ'. (М), Метод. Пусть и=и,а, ... а,. Найти последовательно состояния д, — 6 (у„, и,), дР = 6 (ц„иг),..., д„= 6 (д„„а„). Если у, Е Р, сказать,ДА"; если у„(Р, сказать „НЕТ". П Корректность алгоритма 2.3 слишком очевидна, чтобы ее обсуждать. Однако стоит обсудить временную н емкостную сложности этога алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
