Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 67
Текст из файла (страница 67)
автомата, для которого 6(и, а) определена неоднозначно; точнее, значе- нием б(д, а) является подмножество Я (быть может, пус- тое). Иначе говоря, при фиксированной вершине д симво- лу а соответствует множество ребер, а слову а — множест- во путей, ведущих из в; на каждом шаге недетерминиро- ванный автомат как бы совершает выбор из возможных ребер (д,а). Понятие представимости в недетерминпровап- ном автомате совпадает с понятием представимости в ис- точнике. Теорема 8.7 (теорема детерминизации). Для любого источника Н с и вершинами существует эквивалентный ему детерминированный источник Н', имеющий не более чем 2" вершин. Назовем множество в вершин источника замкнутым, если из того, что д;енд, следует, что д принадлежит любая вершина, в которую из д; ведет пустое ребро.
Для источни- ка без пустых ребер все множества вершин замкнуты. Обо- значим через д, наименьшее замкнутое множество вершин Н, содержащее все начальные вершины Н, Источник Н' строится так. Образуем все замкнутые под- множества вершин Н (их не более чем 2") и каждому тако- 21 — 750 321 му подмножеству поставим в соответствие вершину Н' (в дальнейшем эти подмножества и соответствующие нм вершины будем отождествлять и обозначать д;). Начальной вершиной Н' объявим дм заключительными вершинами — все подмножества дь содержащие хотя бы одну заключительную вершину Н, Если в источнике Н из множества вершин д; пути а (они могут содержать пустые ребра) ведут в множество д~ (т.
е. д~ — это множество концов всех ребер а, начала которых принадлежат множеству д;), то в источнике Н' из вершины д; проводится ребро а в вершину дь Если же в Н никакая из вершин множества д, не имеет выходящего из нее пути а, то в Н' из вершины д~ проводится ребро а в вершину И, соответствующую пустому подмножеству вершин Н. Таким образом, каждой вершине д; источника Н' и каждому входному символу а соответствует ровно одно ребро а, выходящее из вершины д;, и, следовательно, источник Н' — детерминированный.
Другими словами, Н' — это граф автомата с начальным состоянием д~, описанное ранее построение ребер Н' определяет функцию переходов автомата: Ва (дь а) =д~. Источник Н' обладает следующим свойством: в Н' непустой путь а из д~ в д~ существует тогда и только тогда, когда в Н для любой вершины д~д; существует путь а из некоторой начальной вершины д,сна, в д. (Если а=а, то д;=д~ по условию замкнутости; пустых ребер в Н' по построению нет.) Доказательство проведем индукцией по длине слова и. Если а=а, то это свойство выполняется по построению ребер а в Н'. Предположим,что оно выполняется для всех слов а длины (й, и докажем, что оно выполняется для аа, где а — произвольный входной символ.
Пусть в Н' имеется непустой путь аа из д1 в д~. Ва(дь аа) =д~. Если Ва(дь а) =д~, то из д~ в д~ ведет ребро а. По предположению, в Н для любой вершины д*енд~ существует путь а из некоторой начальной вершины д, в д". По построению Н' из того, что в Н' есть ребро а из д~ в дп сле- 322 дует, что в Н для любой вершины деид~ найдется вершина дь из которой ведет путь а в д; поэтому в Н имеется путь а нз о* в д и, следовательно, путь яа из д, в д. Аналогично доказывается обратное утверждение: в предположении, что в Н для любой вершины бенд~ есть путь аа из некоторой начальной вершины д~~д, в д, рассматривается множество всех путей иа из начальных вершин в вершины из д, и множество д~ всех вершин, в которые ведут отрезки и этих путей, С использованием индуктивного предположения и построения ребер Н' показывается, что в Н' 8 (д~, аа) = уь Из доказанного свойства Н' и определения заключительных вершин Н' следует, что в Н' путь и нз д~ в заклю. чительную вершину существует тогда и только тогда, когда в Н имеется путь и из начальной вершины в заключительную.
Поэтому аеиЕ', если н только если а~Е. П Из теорем 8.6 и 8.7 непосредственно следует одна из важнейших теорем теории автоматов, доказанная впервые Клики. Теорема 8.8 (теорема синтеза). Для любого регулярного события Е существует конечный автомат, представляющий это событие. П Метод построения (синтеза) автомата, представляющего Е, заключается в том, что сначала строится источник, представляющий Е, а затем этот источник детермииизнруется путем процедуры, описанной при доказательстве теоремы 8.7. На практике процедура детерминизации несколько модифицируется с целью ее упрощения. Дело в том, что некоторые подмножества вершин Н (т.
е. состояния Н') на достижимы из начальной вершины; их удаление не изменит события, представляемого источником. Поэтому в таблицу переходов Н' включаются только те подмножества, которые порождаются процедурой детермннизации, начатой с подмножества д~ (см. пример 8.8). При такой модификации построенный автомат может иметь меньше чем 2" состояний (и — число вершин исходного источника). Однако в общем случае зту оценку понизить нельзя.
Например, в трехбуквенном алфавите для любого и существует источник с п состояниями, такой, чтолюбой эквивалентный ему автомат имеет не менее чем 2" состояний. Пример такого источника для л=5 приведен на Рис. 8.7 Рис. 8.8 5 7 5 5 5 7 5 4 7 8 4 7 8 7 7 3 6 7 3 3 3 7 3 и) рис.
8.7; доказательство того, что он обладает указанным свойством, можно найти в (171 Пример 8.8. Построим автомат, представляющий событие (абЦс') (а()бс)*а, В соответствии с ранее изложенным синтез автомата проводится в два этапа. Сначала по собы. тню строится представляющий его источник Н. Он изображен на рнс. 8.8. В этом источнике ребра, которым не приписано букв, — пустые; некоторые «лишние» пустые ребра, возникающие, если строго следовать методу теоремы 8.6, удалены. Вершина 1 является начальной, вершина б — заключительной. Затем методом теоремы 8.7 построенный источник детерминизируется, при этом строятся только подмножества, достижимые из начального подмножества (1). Функция переходов детерминированного источника Н', вершинами которого служат подмножества вершин Н, приведена на табл.
8.7,а (знаком Я, как обычно, обозначено пустое множество); после перенумерации этих подмножеств она приобретает обычный вид таблицы переходов (табл. 8.7,6). Таблица 8,7 В табл. 8.7, б заключительные состояния 2 и 5 выделе- ны; они соответствуют подмножествам из табл. 8.7, а, содер- жащим заключительное состояние 6 источника Н.
Анализ автоматов. Если процесс построения автомата по заданному событию (и вообще по некоторому описанию множества слов во входном алфавите) называется синте- зом, то обратный процесс — получения описания множе- ства входных слов, представимого заданным автоматом, на. зывается анализом автомата. Из теоремы 8.9 видно, что ре- зультат анализа также может быть описан с помощью регулярных событий (этот факт также доказан Клинн). Теорема 8.9 (теорема анализа). Всякое событие, пред- ставимое конечным автоматом, регулярно. Определим индуктивно событие Е»: 1) Ео — множе- ство всех входных символов а, таких, что б(111, а) = !11; 2) Ег = Е,',-' () Е»„— ' (Е»; )" Е»-.'. Обозначим через М» !I и -Я Ы»! г! множество всех входных слов, ведущих из йч в 11! и не про- ходящих при этом через состояния с номерами большими, чем /г.
Лемма. Е",.=М», и Докажем зту лемму цо индукции. Для а=О она оче- видна. Пусть она верна для я=г — 1. Тогда М;,. =Е; —.'() М;,. где М,'; — множество всех слов из М1„проходящих через д,. Если аенМ!! и проходит через д„з раз, то а представнг — ! г — 1 МО В Вядс М= ОООО»1...!Хг-!О!и Гдс СООЕ=Си, О»Ос=С~!, П!".Пг-1Е= г — 1 енЕг, (т. е. содержит з — 1 цикл, проходящий через (!г), Поэтому аЕ— : Е!.1(Е:.1) Е И наоборот, если это включение выполнено, то из регулярной формулы его правой части и индуктивного предпог ложения следует, что а~М';!.
Таким образом, Мп = Ес-' (Е'-')* Е'-.' и, следовательно, М'.. = Е'.—.' () Е'-' гг гг ц' г! и !г (Е',— ')» Е' — ' = Е,', что и доказывает лемму. Очевидно, что для автомата с п состояниями, начальным состоянием 11! и заключительными состояниями 14, „,, 11, представляемое им событие имеет внд М"„1()..4М1,», Из леммы следует, что это событие регулярно.
П Доказательство теоремы по существу представляет со- 32$ бой алгоритм анализа. Изложенный здесь алгоритм (алгоритм Макнотона — Ямалы) очень компактен и удобен для доказательств, однако приводит, как, впрочем, и другие алгоритмы анализа, к довольно громоздким регулярным выражениям (прнмер анализа в [14), т. 11). Заметим при этом, что в алгебре регулярных событий нет нетривиальных методов отыскания минимального регулярного выражения, эквивалентного данному. В то же время из теоремы синтеза следует, что проблема распознавания эквивалентности регулярных выражений разрешима, так как по выражениям Еь Ез можно построить представляющие их автоматы 5ь 5р и проверить нх на эквивалентность (сравнив автоматы, минимальные для 5ь 5,); следовательно, метод минимизации регулярных выражений существует, хотя он заведомо нереалистичен из-за своей громоздкости.
Итак, теоремы анализа и синтеза устанавливают взаимно однозначное соответствие между автоматами (с точностью до эквивалентности) и регулярными событиями. Поэтому регулярные события — это один из основных языков для описания поведения автоматов, используемых в теоретических исследованиях.
Важным свойством регулярных событий является их замкнутость относительно булевых операций: пересечение регулярных событий и дополнение к регулярному событию также регулярны (объединенне— регулярная операция по определению). Действительно, если событие Е описывается источником Н, то Е описываеТся источником Й, который отличается от Н тем, что заключи. тельными вершинами Н служат те и только те вершины„ которые не являются заключительными в Н. Так как для любых множеств Е и Е, ЕЯЕз=Е,(~Еь, то из источников для Е, и Еа можно построить источник для Е ()Ез, в силу теорем синтеза и анализа всякое событие, заданное источником, регулярно и искомая замкнутость доказана, Этот факт позволяет расширить язык регулярных событий, дополнив его операциями дополнения и пересечения Пример 8.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
