Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 66
Текст из файла (страница 66)
Рас31б смотрим класс всех вычислимых функций с областью значений вА'. (Фиксация алфавита А не нарушаетобщности, так как значения любых других вычислимых функций можно эффективно кодировать словами из А>.) Каждую функцию из этого класса можно считать функцией, перечисляющей некоторое подмножество А*, т.е.
событие в алфавите А. Тогда в силу теоремы Райса не существует алгоритма, который по данной функции определяет, предста. вимо ли в конечном автомате множество, перечислимое этой функцией, или нет. Поэтому не имеет смысла описывать множества, представимые автоматами, в терминах произвольных разрешимых множеств; следует искать более слабые средства их описания. К изучению таких средств мы н пе еходим.
Х лгебра регулярных событий. Пусть даны события Е, н Ее в алфавите А. Напомним три операции над событиями (языкамн), введенные в гл. 7. 1, Объединение Е>()Ег (обычное объединение множеств). 2. Умножение (конкатенация) Е,Е2.'Е=Е~Ет — это множество всех слов вида а~ам где а>еиЕ» алЕ» 3. Итерация Е,=е()Е,()Е,Е>()...0(Е~) "()...= () Е» с-о События (аД, где а>енА, будем называть элементарными н обозначать просто буквами аь К элементарным отнесем также событие е.
Событие называется регулярным, если оно может быть построено из элементарных событий с помощью конечного числа применений объединения, умножения и итерации; эти операции также назовем регулярными, Иначе говоря, класс Е регулярных событий — это наименьший класс подмножеств А*, содержащий все множества (а,), а также е и замкнутый относительно регулярных операций. Тем самым определена алгебра Я; (), ., *), основным множеством которой является некоторая система подмножеств А*, а именно — класс Я регулярных событий; элементарные события — образующие этой алгебры. Из определения следует, что каждый элемент этой алгебры (т. е: регулярное событие) может быть описан формулой, содержащей символы образующих (е и буквы А) и знаки регулярных операций пад ними. Такие формулы называются регулярными выражениями.
Регулярные выражения эквивалентны, если они описывают одно и то же регулярное событие. Приведем некоторые эквивалентные соотношения в алгебре регулярных событий. Если Е, Еь Ев Ез — регулярные события, то Е~(Ез0Ез) =ЕтЕт0ЕтЕз' (8. 7) (Ет0Ез) Еа = ЕзЕа0 Е2Ее' (8.8) (8.9) (Ех)е = Ее. (8.10) Е" = е0 Е(Е)~. (8,1 1) Кроме того, напомним, что объединение ассоциативно и коммутативно. Пример 8.7.
а. Давно употребляемое нами обозначение Ае для множества всех слов в алфавите А может теперь показаться двусмысленным, поскольку е обозначает итерацию. Однако оба смысла этого обозначения совпадают: регулярное выражение (аД...0а„) е действительно задает множество всех слов (включая пустое) в алфавите А. б, Множество, состоящее из одного слова ац...аоя является регулярным событием, поскольку любое выражение вида ап...а~ регулярно: оно построено из букв с помощью конкатенации. Любое конечное множество слов Е=(аь ...
..., а~) регулярно и описывается выражением Е=а~0...0аы не содержащим итерации, Обратно, если регулярное выражение Е не содержит итерации, то раскрытие скобок (допустимое в силу (8.7) и (8.8)) преобразует его к виду а~0...0аы следовательно, Е описывает конечное событие. Если же Е содержит итера. цию, то оно бесконечно, за исключением случаев, когда итерация применяется только к е (е*=е, т.
е. конечно). в. Регулярное выражение вида А*Е, где Š— конечное событие, не содержащее пустого слова, описывает бесконечное событие, содержащее все слова из А", кончающиеся словами из Е. Такие события называются определенными, или дефинитными. Например, событие (а0Ь0с)'(а0сЬ) содержит все слова в алфавите (а, Ь, с), кончающиеся на а или сЬ. г. Событие Е,=(а0Ь)*с(а0Ь)*с(а0Ь)' состоит из всех слов в алфавите (а, Ь, с), содержащих с ровно 2 раза. Событие Е; состоит из всех слов, содержащих с четное число раз. д.
Регулярное событие Е называется асинхронным событием, если для любых слов аь ат и буквы а из того, что а~а~азяЕ для некоторого Ь, следует, что а,а'аяЕ для любого Ь 1, 2 ...; иначе говоря, если аенЕ, то в Е содер- 316 жатся все слова, полученные из а повторениями некоторых букв слова а, либо вычеркиванием из а некоторых повторений букв. Например; если Š— асинхронное событие и аЬЬсссЫЕ, то аЬсг)еЕ, ааЬссг)г(еЕ и т. д. Регулярные выражения для асинхронных событий могут быть построены из событий аа' с помощью тех же трех операций; прн этом они не должны содержать подформул вида па~па'.
Например, событие (аа*ЬЬ~осс")* асинхронно, а событие (пасс*осе~)* не является асинхронным, так как оно содержит слово пас, но не содержит слова ас, получающегося из пас вычеркиванием повторения а. Регулярные события тесно связаны с автоматами. Изучение этой связи удобно вести, используя описание событий с помощью графов, к которому мы сейчас и переходим. Источники.
Уже говорилось, что на графе автомата событие, представляемое автоматом, изображается множеством путей из начальной вершины в заключительные вершины. Аналогичным образом для описания множеств слов можно использовать произвольные графы (не обязательно автоматные), на ребрах которых написаны буквы. Такие графы называются источниками. Более точно, источником над алфавитом А называется ориентированный граф, в котором: 1) выделены начальные и заключительные вершины (вершина может быть одновременно и начальной, и заключительной); 2) на каждом ребре написана либо буква из А, либо пустое слово е (такие ребра назовем пустыми). Каждый источник Н однозначно определяет событие Е в алфавите А, порождаемое множеством всех путей из начальных вершин в заключительные (если путь содержит пустое ребро, то ему соответствует слово ае()=ар).
В этом случае говорят, что источник Н представляет событие Е. Два источника называются эквивалентными, если они представляют одно и то же событие. Граф автомата без выходов — это частный случай источника. Для любого источника Н существует эквивалентный ему двухполюсный источник Нз (с одной начальной и одной заключительной вершиной, которые, впрочем, могуг совпадать), строящийся так. Если в Й имеется несколько начальных вершин, то в Но вводится новая вершина дм которая объявляется единственной начальной вершиной На и соединяется с прежними начальными вершинами Н пустыми ребрами (ребер, заходящих в пм в Нз нет). Если в Н имеется несколько заключительных вершин, то в Нз вводится новая вершина д„которая объявляется единст.
венной заключительной вершиной Но, из прежних заключительных вершин в д, проводятся пустые ребра; ребер, выходящих из д„в Но нет. В остальном Но совпадает с Н. Теорема 8.6. Для любого регулярного события Е существует двухполюсиый источник, представляющий Е. Теорема доказывается иидукцией по глубине регулярного события Е.
Элементарное событие представляется источником, состоящим из двух вершин — начальной и заключительной и ребра,,идущего из начальной вершины в заключительную, на котором написано данное событие (ао или е). Пусть теперь построены двухполюсные источники: Нь представляющий регулярное событие Еь и Н,, представляющий регулярное событие Е', их начальные вершины — д1о и д,о, заключительные вершины — д„и до, соответственно. Тогда источник Н с начальной вершиной до и заключительной вершиной и„ который представляет событиеŠ†.результат регулярной операции над Е, и Ео, строится так.
1. Е=Е~()Е» Н строится «параллельным соединением» Н~ и Но (рис. 8.6, а), Он состоит из источников Но и Нх бог Чго чх о Рис. б,б и новых вершин до и д,; из до проводятся пустые ребра в 0~о и доо, из г)м и до, проводятся пустые ребра в д,, 2. Е Е,Е,. Н строится «последовательным соединением» Н1 и Но (рис. 8.6, б): из а„ проводится пустое ребро в д,о, начальной вершиной Н объявляется д~о, заключительной вершиной Н объявляется до,. 3. Е=Еь Н строится зацикливанием Н~ (рис. 8.6,в): из д„проводится пустое ребро в 0~о, д~о объявляется начальной и заключительной вершиной Н.
Доказательство того, что построенные таким образом источники действительно представляют соответствующие 320 события, несложно. Пусть, например, Е=ЕоЕ, и ае=Е, Тогда я=айаг, где а1~Е„а,~Е,, По предположению, Н, представляет Еь Но представляет Ем поэтому существуют путь а, из д~о в ды и путь ао из а»о в до,, Но тогда по по- строению существует путь а1ао из д1о (начальной верши. иы Н) в д„(заключительную вершину Н). И наоборот, всякий путь а из д1о в во, обязательно проходит через д~, и а»о, поэтому он имеет вид а=а1ао, где а1 — путь из 7~о в В„и ао — пУть из доо в 7ьн откУда следУет, что а~енЕ~ и аоенЕо.
Доказательства для объединения и итерации ана- логичны. П Введение пустых ребер (вместо простого склеивания вершин) объясняется необходимостью избежать «ложных путей». Некоторые из введенных пустых ребер в дальней- шем можно удалять, не меняя представляемого события. Детерминизация источников н синтез автоматов. Если источник имеет одну начальную вершину, не содержит пус- тых ребер и удовлетворяет условиям автоматности, то он является графом автомата без выходов. Такой источник часто называют детерминированным источником. Этот те(- мин связан с интерпретацией произвольного источника как недетерминированного автомата [61), т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
