Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 30
Текст из файла (страница 30)
2.2.!3. Покажите, что каждое регулярное множество порождается регулярной грамматикой. Указание: Вто можно сделать несколькими способами. Один из них состоит в том, чтобы применить к праволинейной грамматике 6 последовательность преобразований, которая переведет 6 в эквивалентную регулярную грамматику.
Другой способ — построить регулярную грамматику по конечному автомату. 2,2.!4. Постройте регулярную грамматику для регулярного множества, порождаемого праволинейной грамматикой с прави- лами 2.2.15. Опишите алгоритм, который по данной регулярной грамматике 6 н цепочке св определяет, принадлежит ли и языку 7. (6). 2.2.16. Докажите утверждение (2.2.16) из доказательства теоремы 2.3. 2.2.17. Дополните доказательство леммы 2.7 (ш). Определение. Правило А — и праволинейиой грамматики 6==()э", г, Р, Я) называется беслолеэнылс, если в множестве 2* не существует таких цепочек и и х, что В~" сеА ==:> сви~' юх ГЛ.
2. ЗЛЕМЕ ИТЫ ТЕОРИИ ЯЗЫКОВ зл. Оваиствл Регилярных множеств 2.2.18. Постройте алгоритм, преобразующяй праволииейную грамматику в эквивалентную ей грамматику без бесполезных правил. *2.2.19. Пусть 6 =-([ч[, х, Р, 3) — праволинейная грамматика. Пусть М = (А,,..., А„) и сь, = х, -]- х, +... + х, где А г х А [... ...[х„А,— это все правила вида А; — уА . Положим гх,е=х,+... ... +х„, где А, — х, [... [ х„— эта все правила вида А,. — у, Пусть, наконец, 6 будет системой уравнений в стандартной форме А, = !хге-[-глиА, + а!,А, +... —.; аг„А„. Покажите, чтой(6)— наименьшая неподвижная точка системы Я.
Указание: Воспользуйтесь леммой 2.3, 2.2.20. Покажите, что язык Е,(6) из примера 2.10 — эта множество цепочек в алфавите (0,1), длина которых делится на 3. 2.2.21. Найдите детерминированные и недетерминированиые конечные автоматы для тех множеств из упр. 2.2,1, которые регулярны. 2.2.22. Покажите, что конечный автомат из примера 2.11 допускает язык (О+ 1)'00(0+!)'. 2.2.23. Докажите, что конечный автомат из примера 2.12 допускает язык (ма[а (1, 2, 3) н а входит в в).
2.2.24. Дополните доказательство леммы 2.10(]!!). е2.2.25. Двусторонний конечный автомат состоит из (недетерминированного) управляющего устройства с конечным числам состояний н входной головки„которая может двигаться по входной цепочке влево, вправо или оставаться неподвижной. Покажите, что язык допускается двусторонним конечным автоматом тогда и талька тогда, когда он является регулярным множествам. Указание: Постройте детерминированный односторонний конечный автомат, который, прочитав входную цепочку юФе, помещает во внутреннюю память управляющего устройства конечную таблицу, указывающую для каждого состояния д двустороннего автомзта, в каком состоянии (если таковое существует) ои сойдет с правого конца цепочки ги, начав работу на этом правом конце в состоянии д. *2.2.28. Покажите, что если позволить односторонним конечным автоматам сдвигать входную головку ие на каждом такте, то это не увеличит класса определяемых ими языков.
*е2.2.27. Покажите, что дли любого и существует регулярное множество, которое допускается недетерминированным конечным автоматом с и состояниями, на для распознавания которого детерминированным конечным автоматом требуется 2" состояний. 144 2.2.28. Покажите, что каждый язык, допускаемый двусторонним конечным автоматом с и состояниями, допускается односторонним конечным автоматом с 2"'э'" состояниями. **2.2.29.
Сколько различных языков в алфавите (О, 1) определяются (а) иедетерминироваиными, (б) детерминированными и (в) двусторонними конечными автоматами с двумя 'состояниями? Определение. Множество 5 целых чисел образует ириг[элгетииескую прогрессию, если его можно записать в виде З=(с, с+р, с-[-2р,, с+ !р,,), Пусть З(Е) = (1(!ги(=-1 для некоторого гиЕЦ для любого языка 7,. **2.2.30.
Покажите, что для каждого регулярного языка Х. множество З(7.) можно представить в виде объединения конечного числа арифметических прогрессий. Открытая проблелих 2.2.31. Насколько приведенная в упр. 2.2.28 верхняя граница числа состояний одностороннего автомата, моделирующего двусторонний конечный автомат, близка к наименьшему возможному числу состояний? ') Замечания по литературе Регулярные вырзжения были определены Клики [1956!. Дополнительную инфоризиию о регулярных выражениях нежно найти в работах Млк-Нотоиз и Яызды 11960) и Бжезинского [19621').
Сэлоизз [1966э) опнсэл две системы зксвои для регулирных иырзжений з). Хомский и Миллер [1956) докзззли зквивэлентпость регулярных грзиизтнк и регулярных вырзженнй, з Рабин н Скотт [1959) — эквивзлентпость детерииннровзнных и педетерииннровзнных конечных зитоизтов. Упр. 2.2.25 взято из работ Рабина и Скотта [1959] н Шепердсоиэ [1959).
2.3. СВОЙСТВА РЕГУЛЯРНЫХ МНОЖЕСТВ В этом разделе мы докажем несколько полезных результатов о конечных автоматах и регулярных множествах. Особенно важный результат состоят в том, что для каждого регулярного множества по существу однозначна находится определяющий его конечный автомат с минимальным числом состояний. 2.3,1. Минимизация конечных автоматов По данному конечному автомату М можно найти наименьший эквивалентный ему конечный автомат, исключив все недостижимые состояния и затем склеив лишние состояния. Лишние ') В связи с этой проблемой си, работу Хзртмзннсз [!976].— Прим.перев. ') 0 регулярных вырэжениях изписзно иного, см. моногрзфин, упоиннлеиые в замечаниях по литературе к рззд.
2.3.— Прим. перев. ') В связи с этны см, также работы Редько [1964] и Сэлоивя [19666].— Прим, перев. 147 ГЛ. В. ЭЛЕМЕНТЫ ТЕОРНИ ЯЗЫКОВ 2.3. СВОЙСТВА РЕГУЛЯРНЫХ МНОЖЕСТВ состояния определяются с полющью разбиения множества всех достижимых состояний на классы эквивалентности так, что каж. дый класс содержит неразличимые состояния и выбирается как можно шире. Потом из каждого класса берется один представитель в качестве состояния сакрап!енного, или приведенного, автомата.
Таким способом можно сократить объем автомата М, если М содержит недостижимые состояния нли два и более неразличимых состояний. Мы покажем, что этот приведенный автомат — наименьший из конечных автоматов, распознающих регулярное множество, определяемое первоначальным автоматом М.
Определение. Пусть М=ф, л, 6, д„Р) — конечный автомат, а д4 и д,— различные его состояния. Будем говорить, что цепочка хЕХ* ризличпет состояния д4 и д„если (д„х)( — *(4(„е~, (д„х)~ — *(д4,е) и одно из состояний 4!4 и с4 принадлежит а другое нет. Будем говорить, что 64 и д, й-неризличил4ы, и писать д,=-- Ад„если не существует такой цепочки х, различающей с, и д„у которой ~х~(й. Будем говорить, что состояния е! и 4), йеразличимы„н писать 4!!=с„если они й.неразличимы для любого й) О. Состояние дЕ!е называется недостижимым, если не существует такой входной цепочки х, чта (уо,х)' (д,е).
Автомат М называется ариведенныл4, если в (с нет недостижимых состояний н пет двух неразличимых состояний. Пример 2.!4. Рассмотрим конечный автомат М, диаграмма которого показана на рис. 2.5. еачллв Рес. 2.5. Дввграмма автомата М. Чтобы сократить М, заметим сначала, чта состояния г и Б недостижимы из начального состояния А, так что их можно ани ь. Позднее применяя алгоритм 2.2, мы увидим, чта —,ТЛ И классами эквивалентности отношения — =-- будут (А), (В, ) и (С Е,'. Тогда взяв представителями этих множеств состояния 14В р, 41 и Г соответственно, можно получить конечный автомат, изображенный на рис.
2.6, который является приведенным автоматом, эквивалентным М. Е) Рис. 2.6. Прввелевнмй автомат. Лемма 2.11. Пусть М --(!е, 2, 6, д„г) — конечный автолиип с н состояниями. Состояния д4 и дв неразличимы тогда и только тогда, когда ани (и — 2)-неразличимы. Д о к а з а т е л ь с т в о, Необходимость условия тривиальна. Достаточность тривиальна в тех случаях, когда Г имеет О или н элементов. Поэтому рассмотрим случай, когда число элементов множества г' отлично от О или п.
Покажем, что 4 О -=лв — 4 ~ --.М-З Для этого заметим, что для любых состояний 4!! и д4 (1) у!= — '4!4 тогда и толька тогда, когда с, и у, аба либо принадлежат, либо не принадлежат г, (2) с!==-Ав, тогда н только тогда, когда 4!4=А '4Г4 и 6(в„а) ==" ' 6 (с„а) для всех и Е 2. Отношение =' грубейшее; оно разбивает !е на два класса; Р и !е — Е. Если = — А+'Ф= — А, то оп4ошенне =="'" тоньше, чем ==", т. е. в нем по крайней мере па адин класс эквивалентности больше, чем в =='. Так как каждое из множеств г" и !с — г" содержит не более н — 1 элементов, можно получить ие более н — 2 последовательных утончений отношения = †'. Если = — А"' = = — А для некоторого я то в силу (2) =444 = ==А+' =--.... Таким образом, == †э первое из отношений =', для которых =А"' ==А. 1) Мои!но дать интересную интерпретацию леммы 2.11: если два состояния можно различить, то их можно различить с помощью входной цепочки, длина которой меньше числа состояний конечного автомата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
