Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 32
Текст из файла (страница 32)
Естественнымн мерами сложности в данном случае служат число шагов н число ячеек памяти, требуемых вычислительной машине с произвольным доступом к памяти„ у которой каждая ячейка памяти может хранить целое число произвольной величины. (Фактически е реальных вычислительных машинах величина чисел ограничена, но эта граница так велика, чта, несомненно, для тех конечнь!х автоматое, которые имеет смысл рассматривать, она никогда не будет достигнута. Таким Образом, предположение о неограниченности чнсел является здесь разумным математическим упрощением,) Легко видеть, что время рабогы алгоритма линейно зависит от длины цепочки.
Однако пе совсем ясно„влияет ли на Время рабаты „объем" автомата М. Мы должны предположить, что фак- тически описание автомата М представляет собой цепочку символов, взятых из некоторого конечного алфавита. Поэтому можно предположить, что именами состояний являются у4, у„..., уо ..., где индексы записаны в виде двоичных 'чисел, Аналогично обстоит дело с именами входных символов и„а„....
Если предполагается маши!а обычного тнпз, то для хранения функции 6 можно построить двумерный массив, такой, что в ячейке (1,1) находится 6(ун и ). Итак, общее время работы алгоритма будет состоять из времени, необходнмога для построения этой таблицы, которое пропорционально длине описания М, н времени выполнения самого алгоритма, которое пропорциональна (из~. Требуемый объем памяти — это главным образом число ячеек, необходимых для хранения таблицы, оно пропорционально длине описания М. Теперь дадим алгоритмы решения проблем пустоты и эквивалентности, когда описаниями языков служат конечные автоматы.
Алгоритм 2.4. Решение проблемы пустоты для конечных авто матов. Вход. Конечный автомат М вЂ” (!е, Е, 6, у„г). Выход.,ДА", если В (М):~ ЕГ, „НЕТ" в противном случае. Метод. Вычислить множество состояний, достижимых из д4. Если эта множество содержит какое-нибудь заключительное состояние, то сказать,ДА", в противном случае сказать „НЕТ".
Е) Алгоритм 25. Решение проблемы эквивалентности для конечных автоматов. Вход. Два конечных автомата М, =- (()„Х„б„у„Р,) М,=(С(„ХГР б,„у„Р,), таких, что !Е, 1) !Е',= 8. Выход.,ДА", еслй 1. (М„) — Е (М,), „НЕТ" в противном случае. Метод. Построить конечный автомат М=(а,()а~ Е,ОХ~ 6,()6~ дг, Р,()Р,) С помощью леммы 2.11 определить, различимы ли состояния дг и д,. Если да, та сказать „НЕТ'*, в противном случае сказать ,ДА". г) Отметим, что для решения проблемы эквивалентности можно было бы воспользоваться алгоритмом 2.
4, так как Е (М,) = Ь (М,) тогда н только тогда, когда (В (М,) 0 Т. (М,)) 0 (В (М,) П Т. (М,)) = !Гз Теперь займемся вопросом разрешимости проблем принадлежности, пустоты и эквивалентности в тех случаях, когда регулярные множества представляются регулярными выражениями гл. я элвмв нты твогии языков УПРАЖН В Н Н Я или праволинейными грамматиками. Легко показать, что для этих способов представления языков все три проблемы тоже разрешимы. Регулярное выражение можно превратить в эквивалентный конечный автомат с помощью алгоритма, который извлекается из доказательств лемм 2.9 и 2.10. Затем к полученному автомату можно применить один из алгоритмов 2.3 — 2.5.
Праволинейную грамматику можно превратить в эквивалентное регулярное выражение с помощью алгоритма 2.1 и алгоритма, который неявно содержится в доказательстве теоремы 2.2. Ясно, что эти алгоритмы слишком непрямые, чтобы их можно было использовать на практике. Прямые быстро работающие алгорятмы будут предметом нескольких упражнений. Сформулируем эти результаты в виде теоремы. Теорема 2.10. Если леножества определяются конечными автоматами, регулярными выражениями или праволинейными грамлштиками, то проблемы принадлежности, пустоты и эквивалентности для регулярных множеств алгоритлшчески разреигимы, ЕЗ Подчеркнем, что эти три проблемы разрешимы не для любого способа представления регулярных множеств.
Рассмотрим, в частности, следующий пример. Пример 2.17. Можно устроить перечисление машин Тьюринга (см. упражнения к равд. 0.4) в виде списка М;, М„.... Затем можно определить представление регулярных множеств с помощью натуральных чисел, а именно (1) если М, допускает регулярное множество, то пусть число 1 представляет это множество, (2) если М, допускает не регулярное множество, то пусть число 1 представляет множество (е). Каждое положительное целое число представляет, таким образом, некогорое регулярное множество, и каждое регулярное множество представляется хотя бы одним таким числом.
Известно, что для использованного здесь представления машин Тьюринга проблема пустоты неразрешима (упр. 0.4.15). Допустим, что разрешима проблема: „Представляет ли число 1 пустое множество 8?" Легко видеть, что машина М, допускает 8 тогда и только тогда, когда число 1 представляет 8. Следовательно, если регулярные множества определяются только что описанным способом, то проблема пустоты для них неразрешима, Д УПРАЖНЕНИЯ 2 3,1. Дан конечный автомат с и достижимыми состояниями.
Каково наименьшее число состояний эквивалентного ему приведенного автомата? 2.3.2. Найдите конечный автомат с минимальным числом состояний для языка, определяемого автоматом М =((А, В, С, Ю, Е, г), (О, 1), 6, А, (Е, Г)), где функция 6 задается табл. 2А. Тоолияа 2.4 Вход Состояние А В С 0 Е Е В С Е Е Л А Е Е О Е О, Е Определение. Отношение Е назовем грубеишвм правоинвариантным отношением эквивалентности для языка Ес=Х*, если хЕу тогда и только тогда, когда для всех гчХ* цепочка хг принадлежит Е в точности в тех случаях, когда уз ЕЕ. Следующее упражнение устанавливает, что каждое правоинвариантное отношение эквивалентности, определяющее язык Е, содержится в Е. 2.3.6.
Пусть Š†объединен некоторых классов эквивалентности правоинвариаитного отношения эквивалентности )?, опре- 157 2.3.3. Покажите, что для любого и существует такой конечный автомат с п состояниями, что =" '~= — " '. 2.3.4. Докажите„что для автомата М', который строится алгоритмом 2.2, Е(М') =Е(М). Определение. Отношение )?, определенное на Х", называется правоинвариантным, если хлс у влечет хг)?уг для всех х, у, г из Х*. 2,3,5. Покажите, что Š— регулярное множество тогда и только тогда, когда Е можно представить в виде объединения некоторого числа классов эквивалентности правоинвариантного отношения эквивалентности )? конечного индекса. Указание: Для доказательства необходимости определите отношение )?, положивх)?утогда и толькотогда когда(д, х) ) — "(р е) (ое у) ) — '(у е) и р=у (т.
е. цепочки х н у переводят конечиыи автомат, определяющий Е, в одно и то же состояние). Покажите, что )?— правоинвариантное отношение эквивалентности конечного индекса. Для доказательства достаточности постройте конечный автомат, определяющий Е, беря в качестве его состояний классы эквивалентности отношения 1?. ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ У! !РЛЖНЕ ННЯ деленного на Ха.
Пусть Е-- грубейшее правоинварвантное отношение эквивалентности для языка Е.. Покажите, что Е Я. "2.3.7. Покажите, что грубейшее правоинвариантное отношение эквивалентности для языка Е имеет конечный индекс тогда и только тогда, когда Š— регулярное множество. 2.3.8. Пусть М=ф, Х, 6, д„г") — приведенный конечный автомат. Определим отношение Е на Х*, положив хЕу тогда и только тогда, когда (у„х) )-"(р, е), (а„у) ) — а(а, е) и р=а.
Покажите, что Š— грубейшее правоинвариантное отношение эквивалентности для Е (М). Определение. Отношение эквивалентности я на Еа называется отношением конеруэнтнгети, если Я одновременно лево- и правоинвариантно (т. е. если х)ху, то и!хгйгеуг для всех и!, х, у, г из Х*), 2.3.9. Покажите, что !.— регулярное множество тогда и только тогда, когда Е можно представить в виде объединения некоторых классов эквивалентности отношения конгруэнтности конечного индекса. 2,3.10. Покажите, что если М, и М,— приведенные конечные автоматы, для которых Е(М,) =Е(М,), то их диаграммы равны. *2 3.11.
Покажите, что нижняя граница временной сложности алгоритма 2.2 равна а' (т. е. существует такой автомат М с а состояниями, что алгоритму 2,2 требуется произвести аа операций, чтобы найти приведенный автомат, эквивалентнын М). Какова верхняя граница временнбй сложности алгоритма 2.22 Можно найти алгоритм минимизации числа состояний конечного автомата, время работы которого всегда пе превосходит л 1оп л, где а — число состояний минимизируемого автомата. Больше всего времени требует тот этап алгоритма 2.2, который на шаге 2 находит классы эквивалентности отношения ==- методом леммы 2.11.
Однако на шаге 2 можно использовать другой алгоритм, который позволяет сократить время работы алгоритма 2.2 до а!ода. Этот новый алгоритм несколько иначе, чем в лемме 2.11, измельчает разбиения множества состояний. Вначале все состояння разбиты на заключительные и незаключительпые. Далее допустим, что некоторое разбиение состоит из классов л„л„... ..., л„,. Для того чтобы сделать это разбиение более мелким, выберем класс л! и входной символ а. Каждый класс л!, содержащий такое состояние у, что 6 (у, а) ~ л!, расщспляется на два класса: я!2=-(а ~ дЕл и 6(а, а) ~л!) и л1=л — л';. Таким обра15а зом, в отличие от метода леммы 2.11 здесь происходит расщепление класса, как только выясняется, что данный вход переводит некоторые состояния этого класса в такие, неэквивалентность которых установлена ранее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
