Математическая теория систем. Математические основы теории систем
 Скачать 2.07 Mb.
|
|
х 2 ∈ Е 2 . По условию Н 1 представляет Е 1 , Н 2 представляет Е 2 , поэтому существует путь х 1 из q 01 в q z1 и путь х 2 из q 02 в q z2 . Тогда по построению существует путь е х 1 е ∪ е х 2 е= х 1 ∪х 2 из вершины q 0 в вершину q z . И наоборот, всякий путь х из q 0 в q z обязатель- но проходит через q 01 и q z1 либо через q 02 и q z2 и имеет вид х = х 1 ∪х 2 , где х 1 – путь из q 01 в q z1 , а х 2 – путь из q 02 в q z2 , откуда следует, что х 1 ∈ Е 1 и х 2 ∈ Е 2 . Что и требовалось доказать. При построении источника в некоторых случаях необходимо вводить пустые ребра (ребра, взвешенные пустой буквой e). Это делается для то- го, чтобы избежать ложных путей. Система правил, когда следует вво- дить пустые ребра в граф регулярного выражения, следующая. 1. Пустые ребра вводятся в случае произведения двух или более ите- раций * ( ) i i N S R ∈ = ∏ (рис. 2.5.), где R i – регулярные выражения. 2. Пустые ребра в источнике, представляющем событие S, когда регу- лярное выражение для S начинается или заканчивается итерацией, вво- дятся в случаях: а) S=(P * ⋅R) * ; б) S=(R⋅N * ) * ; в) S=(P * ⋅R⋅N * ) * Здесь R, P и N – произвольные регулярные выражения. Соответствующие графы изображены на рис. 2.6. R 2 R 1 R N q 0 е …. q z Рис. 2.5. Введение пустых ребер при произведении итераций 72 3. Пустые ребра вводятся в случае дизъюнкции, если хотя бы один из дизъюнктивных членов начинается с итерации * * S R Q P Q = ⋅ ∪ ∪ ∪ , где Q – регулярное выражение, не содержащее итерации (рис. 2.7). 4. Пустые ребра вводятся при умножении слева на дизъюнкцию, если хотя бы один из дизъюнктивных членов заканчивается итерацией (рис. 2.8.) ( ) * * S Q R P Q N = ⋅ ∪ ∪ ∪ ⋅ . Рис. 2.6. Введение пустых ребер при итерации R P q 0 ( q z ) е а) R N е q б) q 0 ( q z ) е R P N в) q 0 ( q z ) e R P е е Q Q q q z3 q z1 q Рис. 2.7. Введение пустых ребер в случае дизъюнкции 73 Перечисленная система правил является полной, т.е. ни в каких дру- гих случаях вводить пустые ребра нет необходимости. Это нетрудно по- казать, рассматривая всевозможные сочетания операций ( ∪ , • , *) в регу- лярном выражении. 2.3.3. Синтез автоматов (абстрактный уровень) Перейдем теперь к синтезу автоматов, т.е., по сути, к доказательству теоремы 2.3.2 а. Вначале введем понятие детерминированного источника. Речь уже шла о том, что автомат без выходов – это частный случай источника. Ис- точник будет являться графом автомата без выходов, если он: а) содер- жит одну начальную вершину; б) не содержит пустых ребер и в) удовле- творяет условиям автоматности. Такой источник и назовем детерминиро- ванным источником в отличие от произвольного недетерминированного источника. Это название связано с тем, что произвольный источник мож- но интерпретировать как недетерминированный автомат, т. е. как авто- мат, в котором функция переходов ( ) , q x δ может иметь несколько значе- ний (символу х при вершине q можетсоответствовать множество ребер, а слову х – множество путей из вершины q). Теперь докажем вспомогательную теорему. Теорема 2.3.4 (детерминизации). Для любого источника Н с n верши- нами существует эквивалентный ему детерминированный источник Н', имеющий не более чем 2 n вершин. Доказательство . Назовем множество вершин qɶ замкнутым, если из того, что q i ∈ qɶ , следует, что qɶ принадлежит любая вершина, в которую R P е е е Q Q q 0 N q z Рис. 2.8. Введение пустых ребер при умножении на дизъюнкцию 74 из q i ведет пустое ребро. Таким образом, для источника без пустых ребер любое множество вершин замкнуто. Источник Н' строится следующим образом. Образуем все замкнутые подмножества вершин Н (а их не более чем 2 n ) и каждому такому под- множеству поставим в соответствие вершину i qɶ источника Н'. Через 0 qɶ обозначим наименьшее замкнутое подмножество вершин Н, содержащее все начальные вершины Н. Это будет начальная вершина Н'. Заключительными вершинами Н' объявим все подмножества i qɶ , содержащее хотя бы одну заключитель- ную вершину Н. Если из множества i qɶ источника Н есть пути х (х ∈ Х) в множество j qɶ , то в источнике Н' соединяем вершину i qɶ с вершиной j qɶ ребром, на котором написан символ х. Если же в Н никакая из вершин i qɶ не имеет выходящего из нее ребра с символом х, то соединяем вершину i qɶ в Н' с вершиной Ø (пустое подмножество вершин Н) ребром х. Таким образом, каждой вершине i qɶ в Н' и каждому символу х соответствует ровно одно ребро х, выходящее из i qɶ , и источник Н' является детермини- рованным. Построение ребер Н' определяет функцию перехода автомата, граф которого – это источник Н'. Начальное состояние этого автомата 0 qɶ . Осталось показать, что источник Н' эквивалентен Н. Действительно, Н' обладает свойством: в Н' непустой путь x из 0 qɶ в j qɶ существует тогда и только тогда, когда в Н для любой вершины j q q ∈ ɶ существует путь x из некоторой начальной вершины 0 0 q q ∈ ɶ в q. Пустым путь x быть не может, так как, если x =е, то 0 j q q = ɶ ɶ по условию замкнутости, а в Н' пу- стых ребер по построению нет. Это свойство доказывается индукцией по длине слова x . Если x =х (состоит из одного символа), то это свойство выполняется по построению ребер в Н'. Предположим теперь, что оно выполняется и для слова длины, меньшей или равной k, и докажем, что оно выполняется и для слова x х, где х ∈ Х произвольная буква входного алфавита. Пусть в Н' имеется непустой путь x х из 0 qɶ в j qɶ : ( ) 0 , j q x q δ = x ɶ ɶ . Если ( ) 0 , k q q δ = x ɶ ɶ , то из k qɶ в j qɶ ведет ребро х. По предположению, в Н для любой вершины q* ∈ 0 qɶ существует путь x из начальной вершины q 0 в q*. 75 По построению Н' из того, что в Н' есть ребро х из k qɶ в j qɶ , следует, что в Н для любой вершины q ∈ i qɶ найдется вершина из подмножества k qɶ , из которой ведет путь х в q, поэтому в Н имеется путь из q* в q и, следова- тельно, путь x х из q 0 в q. И наоборот, если в Н для любой вершины q ∈ i qɶ есть путь x х из начальной вершины 0 0 q q ∈ ɶ в вершину q, то в Н' будет выполняться условие ( ) 0 , j q x q δ = x ɶ ɶ . Доказывается это аналогичным образом. При этом рассматривается множество путей x х из начальных вершин Н в вершины множества i qɶ и множества k qɶ всех вершин, в которые ведут отрезки x этих путей. Из доказанного свойства Н' и определения заключительных вершин Н' следует, что в Н' путь x из 0 qɶ в заключительную вершину есть тогда и только тогда, когда в Н имеется путь x из некоторой начальной вершины в заключительную. Следовательно, источники Н и Н' эквивалентны, по- скольку представляют одно и то же событие. Что и требовалось доказать. По сути дела, из доказательства теорем 2.3.3 и 2.3.4 и следует доказа- тельство теоремы синтеза 2.3.2 а, а синтез автомата, представляющего произвольное регулярное событие Е, состоит в том, что сначала строится источник, представляющий Е, а затем этот источник детерминируется согласно процедуре, изложенной при доказательстве теоремы 2.3.4. Практически детерминизация упрощается в связи с тем, что некото- рые подмножества вершин Н (состояния Н') не достижимы из начального состояния и их удаление не изменит события, представляемого автома- том. Поэтому в матрицу переходов Н' включаются только те подмноже- ства, которые порождаются процедурой детерминизации, начатой с под- множества 0 qɶ . В этом случае построенный автомат может иметь меньше чем 2 n состояний. Пример 2.12. Рассмотрим синтез автомата на абстрактном уровне. Ре- гулярное событие, которое должен представлять автомат, может быть задано либо словесным описанием, либо регулярным выражением. Пусть регулярное событие в алфавите { a,b,c}задано выражением ( ) ( ) * * * * ( ) a b c c a b ac ∪ ⋅ ⋅ ∪ ⋅ . (2.3.1) 76 Процедура синтеза начинается с построения источника H. При этом нужно учитывать правила введения пустых ребер. В формуле (2.3.1) име- ется произведение итераций (правило 1); первая скобка представляет со- бой дизъюнкцию, в которой один из дизъюнктивных членов начинается с итерации (правило 3), а также один из дизъюнктивных членов заканчива- ется итерацией (правило 4). Поэтому построенный источник H будет со- держать пустые ребра (см. рис. 2.9). На рис. 2.9 ребра, которым не приписано букв, – пустые. Начальная вершина источника – 1, заключительная – 5. Следующий этап – детерминизация источника H в соответствии с теоремой 2.3.4. При этом строим только замкнутые подмножества, до- стижимые из начального замкнутого подмножества {1,2}. Функция пере- ходов полученного автомата приведена в табл. 2.17. Т а б л и ц а 2 . 1 7 a b c {1,2} {2} {4,5} {3,4,5} {2} {2} {4,5} ∅ {4,5} {4,5,6} {4,5} ∅ {3,4,5} {4,5,6} {4,5} {3,4,5} ∅ ∅ ∅ ∅ {4,5,6} {4,5,6} {4,5} {5} {5} {6} ∅ ∅ {6} ∅ ∅ {5} 1 2 3 4 5 a c a b с b 6 a c Рис. 2.9. Источник, представляющий событие (2.3.1) 77 В этой таблице знаком ∅ обозначено пустое множество. После пере- обозначения подмножеств вершин – {1,2}→1; {2}→2; {4,5}→3; {3,4,5}→4; ∅ →6; {4,5,6}→7; {5}→8; {6}→9 – таблица переходов авто- мата приобретает следующий вид (табл. 2.18). Т а б л и ц а 2 . 1 8 a b c 1 2 3 4 2 2 3 5 3 5 3 5 4 5 3 4 5 5 5 5 6 5 3 7 7 8 5 5 8 5 5 7 В табл. 2.18 выделены жирным шрифтом заключительные состояния 3,4,6 и 7, соответствующие подмножествам из табл. 2.17, содержащим заключительное состояние 5 источника H. 2.3.4. Анализ автоматов (абстрактный уровень) Для процедуры анализа автоматов потребуется ввести несколько но- вых понятий. Ребра и вершины источника, не входящие в контур обрат- ных связей, назовем каскадными. Вершины называются стоком, если они имеют только входящие ребра и истоком, если они имеют только выходящие ребра. Две вершины, лежащие в контуре обратной связи, называются спаренными. Источник, состоящий только из каскадных вершин, называется кас- кадным. Поскольку стоки и истоки всегда каскадные, то любую из вер- шин обратной связи можно сделать каскадной с помощью операции, называемой расщеплением вершины. Произвольная вершина q в этом случае расщепляется на две вершины: q', которая называется истоком, и q'', служащая стоком. Пример такого расщепления приведен на рис. 2.10. Расщепленные вершины называются индексными вершинами. Мини- мальное число вершин, которые нужно расщепить, чтобы разбить все кон- туры обратной связи, называется индексом соединения обратной связи. Граф, изображающий источник, можно упростить, устранив ряд вер- шин и приведя ветвевой переход к значению пути через устраненные 78 вершины. Полученный граф называется остатком первоначального. Вершина, входящая в остаточный граф, называется остаточной. Путь, если он связывает остаточную вершину с собой или с заданной остаточ- ной вершиной и не проходит через другие остаточные вершины, называ- ется остаточным. Исключая в исходном источнике все вершины, кроме истоков, стоков и индексных вершин, получим индексный остаток. Если необходимо сохранить вершину q, не являющуюся ни истоком, ни стоком, ни индекс- ной вершиной, то это можно сделать путем соединения новой вершины q' с вершиной q ребром е и устранением вершины q. В результате получа- ется исток. Аналогичным образом поступают и для образования стока. Существующие методы анализа можно разделить на графические, ис- пользующие понятие источника и его эквивалентные преобразования, и аналитические, в которых применяются уравнения в алгебре регулярных событий. Впервые алгоритм получения регулярных выражений был дан Мак-Нотоном и Ямадой (Мс. Naughton & Yamada) в 1960 г., однако он довольно громоздок и не приводится. Рассмотрим графический алгоритм анализа. Отыскание регулярного выражения, означающего множество слов, переводящих автомат из со- стояния q i в состояние q j , сводится в конечном итоге к нахождению вет- вевого перехода из вершины q i в q j на графе автомата. В этом случае граф автомата приводится к источнику, имеющему только два состояния: q i и q j . Если в начале приведения вершина q i является истоком, q j – стоком, то полученный источник будет иметь только один непустой переход от q i к q j и вес этого перехода будет являться искомым регулярным выражением. При таком приведении остальные вершины должны быть удалены. Например, пусть необходимо удалить в графе вершину q k с петлей t kk (см. рис. 2.11, а). х 3 х 3 х 4 х 4 q а) х 3 q' х 4 х 4 q'' б) Рис. 2.10. Пример расщепления вершины 79 Регулярное выражение, связывающее p q и s q , будет * 1 ( ) pk kk ks R t t t = ⋅ ⋅ , а при устранении вершины q k получим (рис. 2.11, б): * ( ) p s p k k k k s R t t t t = ∪ ⋅ ⋅ Таким образом, любой граф автомата можно свести к источнику с двумя вершинами q i и q j , ветвевой переход между которыми и есть иско- мое регулярное выражение, представимое состоянием q j при условии, что q i – начальное состояние. При анализе граф автомата, как правило, приводят к индексному остатку. Это можно сделать с помощью элементарных преобразований, но на практике используют приведение к индексному остатку с провер- кой по правилу. Это правило заключается в том, что между остаточными вершинами q i и q j в построенном источнике должно быть ребро, если в первоначальном графе есть, по крайней мере, один остаточный путь от q i к q j . Вес такого ребра равен объединению всех приращений остаточных путей от q i к q j . Прирост пути от q i к q j определяется произведением при- ращений ребер, образующих этот путь. Если индексный остаток включает сложный контур обратной связи, устраняемые вершины могут быть исключены расщеплением вершин. При удалении некоторой вершины q k все другие вершины расщепляются на истоки и стоки. Далее вычисляются пути от истока до стока, и рас- щепленные вершины соединяются вновь. |