Главная Промышленная автоматика.

(д) {аР \ р- простое число},

(е) {w\w{0,l}* nw имеет одинаковые числа нулей и единиц}.

2.3.16. Пусть / (т) -монотонно возрастающая функция и для каждого п существует такое т, что f {tn-\-1) f (т) п. Покажите, что множество {a*""mI} не регулярно.

Определение. Пусть Lj и Lg -языки. Определим следующие операции:

(1) LjL2-={w\wxL- для некоторого xL},

(2) IN\T (LJ = {w\wx для некоторого x},

(3) VIN {Lj) = {wlxwLi для некоторого x},

(4) SUB {Lt) = {w\xwy для некоторых x и y\,

(5) MIN {Li) = \w\wL и никакой собственный префикс цепочки W не принадлежит L},

(6) МАХ {L)~ {w\w£Lj и не существует такого .s:б, что wxLj}.

Пример 2.18. Пусть L = {0Н"0\п, т> 1} hL=VO\ Тогда

ljL,=L,U{0V\L> 1, /<t}

L/Z-i = 0 INIT{LJ = ,U{0l/> 1, /<t}UO* FIN(L,) ={0l/0/t>l, />1, i/yul-OUO* SUB (Li) - {010 I / < /} и 1*0* и 0*1* MIN{LJ -{0«l"0n> 1} MAX (L J - 0 □

*2.3.17. Пусть Li и Lg -регулярные множества. Покажите, что следующие множества регулярны:

(а) i/ai

(б) [NIT(f.,), ,

(в) FIN{LJ,

(г) SUB(,),

(д) MIN(LJ,

(е) МАХ (LJ.

*2.3.18. Пусть Li - регулярное множество, а Lg -произвольный язык. Покажите, что множество L/L регулярно. Существует ли алгоритм, который находит конечный автомат для LjL, если дан автомат для L}

Определение. Производную Da регулярного выражения а по х2>* можно определить рекурсивно:

(1) D,a = oc.

(2) Для а €2

(а) D,0-0,

(б) De=0,

если еа, если еау

. ч г. , / афЬ,

(в) U,j3={ , I <з, если а-Ь,

(г) D,(aH-p)D,a-hD,p,

(е) D,a*-(D,a)a% (3) D„a-D(D„a) для 02 и л62*.

2.3.19. Покажите, что если а-10*1, то

(а) D= ЮМ,

(б) D,ot0,

(в) DaOM.

*2.3.20. Покажите, что если а - регулярное выражение, обозначающее регулярное множество R, то Da обозначает

x\R - {w\xwR].

**2.3.21. Пусть L - регулярное множество. Покажите, что множество {x\xyL для некоторого у, такого, что х=у} регулярно.

Следующее упражнение обобщает упр. 2.3.21.

**2.3.22. Пусть L - регулярное множество и /(х) -полином от х с неотрицательными целыми коэффициентами. Покажите, что множество I шу € L для некоторого у, такого, что у = /( tcj])} регулярно.

*2.3.23. Пусть L-регулярное множество и h - гомоморфизм. Покажите, что h{L) и /г (L) -регулярные множества.

2.3.24. Докажите корректность алгоритмов 2.4 и 2.5.

2.3.25. Оцените временную и емкостную сложности алгоритмов 2.4 и 2.5.

2.3.26. Дайте формальное доказательство теоремы 2.10. Обратите внимание, что недостаточно просто показать, что, скажем, для каждого регулярного выражения существует конечный автомат, допускающий обозначаемое им множество. Нужно показать, что существует алгоритм, который по регулярному выражению строит этот автомат. В этой связи см. пример 2.17.

*2.3.27. Дайте эффективный алгоритм минимизации числа СОСТОЯНИЙ не полностью определенного детерминированного конечного автомата.

2.3.28. Дайте эффективные алгоритмы, решающие проблемы принадлежности, пустоты и эквивалентности для (а) регулярных выражений,

А. Ахо, Дж. Ульман, т, I 161



(б) праволинейных грамматик,

(в) недетерминированных конечных автоматов.

**2.3.29. Покажите, что проблемы принадлежности и эквивалентности неразрешимы для способа представления регулярных множеств, указанного в примере 2.17.

*2.3.30. Покажите, что проблема: „Бесконечен ли язык L разрешима для конечных автоматов. Указание: Покажите, что для автомата Men состояниями язык L (М) бесконечен тогда и только тогда, когда L{M) содержит цепочку для которой n\w \ <С2п.

*2.3.31. Докажите алгоритмическую разрешимость проблемы включения L (Mj)L (Мз), где и -конечные автоматы.

Открытая проблема

2.3.32. Найдите быстрый алгоритм (скажем, такой, который для автомата с п состояниями требует времени не более /г*, где k - константа), дающий недетерминированный конечный автомат с минимальным числом состояний, эквивалентный данному.

Упраошения на программирование

2.3.33. Напишите программу, которая воспринимает в качестве входа конечный автомат, праволинейную грамматику нли регулярное выражение и выдает на выходе эквивалентное регулярное выражение, конечный автомат или праволинейную грамматику. С помощью такой программы можно, например, по регулярному выражению построить эквивалентный ему конечный автомат.

2.3.34. Постройте программу, которая воспринимает в качестве входа описание конечного автомата и выдает на выходе эквивалентный ему приведенный автомат.

2.3.35. Напишите программу, которая будет моделировать недетерминированный конечный автомат.

2.3.36. Постройте программу, определяющую, эквивалентны ли два описания регулярного множества (тип описаний надо взять такой, чтобы проблема эквивалентности была разрешима).

Замечания по литературе

Минимизация конечного автомата впервые изучалась Хафменом [1954] и Муром [1956]. Свойства замкнутости регулярных множеств н результаты о разрешимости взяты из статьи [Рабин и Скотт, 1959].

Упражнения содержат лишь некоторые нз многих результатов, касающихся конечных автоматов и регулярных выражений. Алгоритм 2.G взят из

2.4. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ

работы Хопкрофта [1971]. Результат из упр. 2.3.22 получен Косараю [1970]. Производная регулярного выражения была определена Бжозовскнм [1964].

Существует много методов минимизации не полностью определенного конечного автомата (упр. 2.3.27). Эту проблему рассматривали С. Гинзбург [1962] н Пратер [1969]. Частичное решение проблемы, сформулированной в упр. 2.3.32, дано в работе Камеды и Вайнера [1968].

Достаточно полно теория конечных автоматов излагается в книгах Гилла [1962], С. Гинзбурга [1962], Харрисона [1965], Минского [1967], Бута [ 1967], А. Гинзбурга [1968], Арбиба [1969] и Саломаа [1969а]).

Томпсон [1968] описывает технику программирования, полезную при построении распознавателя по регулярному выражению.

2.4. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ

Из четырех классов грамматик иерархии Хомского класс коитекстио-свободных грамматик наиболее важен с точки зрения приложений к языкам программирования и компиляции. С помощью КС-грамматики можно определить большую часть синтаксической структуры языка программирования. Кроме того, она служит основой различных схем задания переводов.

В ходе самого процесса компиляции синтаксическую структуру, придаваемую входной программе КС-грамматикой, можно использовать при построении перевода этой программы. Синтаксическую структуру входной цепочки можно определить по последовательности правил, примененных при выводе этой цепочки. Такнм образом, на часть компилятора, называемую синтаксическим анализатором, можно смотреть как на устройство, которое пытается выяснить, существует ли в некоторой фиксированной КС-грамматике вывод входной цепочки. Однако это нетривиальная задача - но данной КС-грамматнке G и входной цепочке w выяснить, принадлежит ли w языку L{G), и если да, то найти вывод цепочки w в грамматике G. В гл. 4-7 эта проблема будет исследована подробно.

В данном разделе мы построим фундамент, на котором будет основано наше изучение синтаксического анализа. В частности, определим деревья выводов и изучим преобразования, которым можно подвергнуть КС-грамматики, чтобы привести их к более удобному виду.

2.4.1. Деревья выводов

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

Прим пер" книги Глушкова [1962] н Трахтенброта и Барздиня [1970]i



Произвольного вида сложно (см. упражнения к разд. 2.2), но в случае КС-грамматик можно ввести удобное графическое представление класса эквивалентных выводов, называемое деревом вывода.

Дерево вывода в КС-граммагике G = {N, 2, Р, 5) - это помеченное упорядоченное дерево, каждая вершина которого помечена символом из множества NU2U{e-. Если внутренняя вершина помечена символом А, а ее прямые потомки - символами Xj, Xg, ..х„, то А ~>XiXa ... х„ -правило этой грамматики.

Определение. Помеченное упорядоченное дерево D называется деревом вывода (или деревом разбора) в КС-грамматике G {А) = = (N,-2, Р, А), если выполнены следующие условия:

(1) Корень дерева D помечен А.

(2) Если Dj, ..- поддеревья, над которыми доминируют прямые потомки корня дерева, и корень дерева помечен X,-, то А-х ... Х) - правило из множества Р. должно быть деревом вывода в грамматике G (X,-) = (N, 2, Р, X,-), если х-- нетерминал, и состоит из единственной вершины, помеченной X,-, если Х( - терминал.

(3) Если корень дерева имеет единственного потомка, помеченного е, то этот потомок образует дерево, состоящее из единственной вершины, и Л->е -правило из множества Р.

Пример 2.19. На рис. 2.8 изображены деревья выводов в грамматике GG {S) с правилами 5 -aSbS bSaS \е. □

е а


е а

а 5 б . е

Рис. 2.8. Деревья выводов.

Заметим, что существует естественное упорядочение вершин упорядоченного дерева, при котором прямые потомки вершины упорядочиваются „слева направо", как определено в разд. 0.5.4. Расширим это упорядочение следующим образом. Допустим, что /г-вершина и п, ..п-ее прямые потомки. Тогда если / < /, то вершина Л/ и все ее потомки считаются расположенными левее вершины Пу и всех ее потомков. Доказательство непроти-

воречивости этого упорядочения оставляем в качестве упражнения. Надо лишь показать, что либо любые две вершины упорядоченного дерева лежат на одном пути, либо одна из них расположена левее другой.

Определение. Кроной дерева вывода назовем цепочку, которая получится, если выписать слева направо метки листьев.

Например, кроны деревьев выводов, показанных на рис. 2.8, таковы: (а) 5, (б) е, (в) аЪаЪ и (г) аЬаЬ.

Покажем теперь, что деревья выводов адекватно представляют выводы в том смысле, что для каждого вывода выводимой цепочки а в КС-грамматике G можно построить дерево вывода в G с кроной а, и обратно. Для этого введем несколько новых понятий. Пусть D-дерево вывода в КС-грамматике -(N, 2,Р,5).

Определение. Сечением дерева D назовем такое множество С вершин дерева D, что

(1) никакие две вершины из С не лежат на одном пути в D,

(2) ни одну вершину дерева D нельзя добавить "к С, не нарушив свойства (1).

Пример 2.20. Множество вершин дерева, состоящее из одного корня, является сечением. Листья тоже образуют сечение. Еще


е 1 *

Рис. 2,9. Пример сечения

один пример сечения -множество на рис. 2.9, состоящее из вершин дерева, обведенных кружками. □

Определение. Определим крону сечения дерева D как цепочку, которая получается конкатенацией (в порядке слева направо) меток вершин, образующих некоторое сечение.

Например, abaSbS-крона сечения дерева вывода, показанного на рис. 2.9.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [26] 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002