XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 83
Текст из файла (страница 83)
Другими словами, ко всем уравнениям системы, соответствующим заключительным состояниям, добавляется слагаемое Л. Действительно, решение системы (7.6) будет иметь вид 521 7.а детермияяеацяя яонечлых автоматов Исключая хе, получаем < х1 = Ь(ах1 + Ьхг) + ахи хз = а(ах1+ Ьхз) + Ьх1+ Л, откуда ~ ~ ~ 2 ~ ~ е 2 х1 = (Ьа+ а)'Ьзхз хз = (а +6)(Ьа+а)"Ь хг+аЬхз+Л.
Тогда 2 | ~~ ~ ~ 2 е Э 2 | ~ 7 е хз = ((аз+ Ь)(Ьа+ а)" 62 + аЬ)', х| = (Ьа+ а)"Ьз((аз+ Ь)(Ба+ а)'Ьз+ аЬ)". Отсюда получаем регулярное выражение, обозначающее язык конечного автомата, как значение переменной хо: хо = а(6а+а) Ьь((а +Ь)(Ьа+а) Ь +аЬ)"+ + Ь((а + Ь) (Ьа+ а)'Ь + аЬ)'. Как видим, полученное регулярное выражение весьма сложно и найти его, не располагая заранее разработанным алгоритмом, было бы затруднительно. Т.б. Детерминизация конечных автоматов Для дальнейшего изучения свойств коиечиых автомииов и, в частности, для решения задачи синтеза важное значение имеет следующел теорема.
Теорема Т.Т (тпеорема о дееперминизаиии). Для любого конечного автомата может быть построен зквивалемииый ему деевермииироваииый конечный автомат. ч Для того чтобы доказать теорему, нужно, во-первых, описать алгоритм построения детерминированного конечного автомата по исходному; во-вторых, обосновать этот алгоритм, строго доказав, что он действительно дает конечный автомат, 522 Ч. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ ис. 7.11 который является детерминированным и эквивалентным исходному. Здесь мы приведем только сам алгоритм построения детерминированного автомата.
Его обоснование дано в Д.7.1. Преобразование проювольного конечного автомата к эквивалентному детерминированному осуществляется в два этапа: сначала удаляются дуги с ме~икой Л, затем проводится собственно детерминизация. 1. Удаление Л-переводов (дуг с меткой Л). Чтобы перейти от исходного конечного автомата М = = (1; Щ де, г', б) к эквивалентному конечному автомату М' = = (У, Я', де, Р', б') без Л-переходов, достаточно в исходном графе М проделать следующие преобразования. а.
Все состояния, кроме начального, в которые заходят только дуги с меткой Л, удаапотся; тем самым определяетсл множество Я' конечного автомата М'. Понятно, что Я' С Я. Прн этом полагаем, что начальное состояние остается прежним. б. Множество дуг конечного автомата М' и их меток (тем самым и функция переходов М') определяется так: для любых двух состояний р,г Е Я' р -+„г имеет место тогда и только тогда, когда а е У, а в графе М имеет место одно из двух: либо существует дуга иэ р в г, метка которой содержит символ а, либо сУЩествУет такое состолние д, что Р =~1 д и д ~в г.
+ При этом вершина д, вообще говоря, может и не принадлежать множеству Я', т.е. она может и исчезнуть при переходе к автомату М' (рис. 7.П). Если же е Е Ч', Н то, естественно, в М' сохранится дур га (д, г) и символ а будет одним из Р символов, принадлежащих метке этой дуги (рис. 7.12). Таким образом, в М' сохраняются все дуги М, метки которых отличны от Л и которые соединяют пару (вершин) состояний ю множества Я'(не удаляемых согласно п.
а). Кроме этого, для любой тройки состояний р, д, г (не обязательно различных!), 7.б. Детермиииеацив иоиечиьп автоматов 523 такой, что Р, т Е Я' и существует путь ненулевои длины из р в д, метка ко- Р ч торого равна Л (т.е. путь по Л-пере- Ь ходам), а вз д в т ведет дуга, метка которой содержит символ а входного И аафавиепа, в М' строится дуга из р в а т, метка которой содержит символ а и т (см. рис. 7.11). в.
Множество заключительных состояний Р' конечного автомата М' содержит все состояния д Е Я~, т.е. Рис. 7.1е состояния конечного автомата М, не удаляемые согласно п.а, для которых выест место д ФЛ де для некоторо- ОР м ®- го де Е и'(т.е.либо состояние д само Ц является заключительным состояни- ОР ем конечного автомата М, либо из Рис.
7.13 него ведет путь ненулевой длины по дугам с меткой Л в одно из заключительных состояний конечного автомата М) (рис. 7.13). 2. Собственно детерминизация. Пусть М = (Я, т', до, г', 6) — конечный автомат без Л-пеРеходов. Построим эквивалентный М детерминированный конечный автомат М1. Этот конечный автомат определяется таким образом, что его множество состояний есть множество всех подмножеств множества состояний конечного автомата М.
Это значит, что каждое отдельное состояние конечного автомата М1 определено как некоторое подмножество множества состояний конечного автомата М. При этом начальным состоянием нового конечного автомата (т.е. М1) является одноэлементное подмножество, содержащее начальное состояние старого конечного автомата (т.е. М), а заключительными состояниями нового конечного автомата являются все такие подмножества ц, ко- 524 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ торые содержат хотя бы одну заключительную вершину исходного конечного автомата М. Впредь, допускал некоторую вольность речи, мы будем иногда называть состояния конечного автомата М1 состояниями- множествами.
Важно, однако, четко усвоить, что каждое такое состояние множество есть отдельное состояние нового конечного автомата, но никак не множество его состояний. В то же время для исходного („старого") конечного автомата М это именно множество его состояний. Образно говоря, каждое подмножество состояний старого конечного автомата есвертываетсяо в одно состояние нового конечного автомата'. Функция переходов нового конечного автомата определена так, что иэ состояния-множества Я по входному символу а конечный автомат М1 переходит в состояние-множество, представляющее собой объединение всех множеств состояний старого конечного автомата, в которые этот старый конечный автомат переходит по символу а иэ каждого состояния множества о.
Таким образом, конечный автомат М1 является детерминированным по построению. Приведенное выше словесное описание можно перевести в формулы следующим образом: строим конечный автомат М1 так, что М1 = (Я1, У, (до), гм о1), где Я1 = 2ч, Р1 = (,Т: Т О Р ф И, Т Е 2ч ), (уо С ь))(та е У)(д1(о,а) = Ц 6(д,а)). (7.Е) 'Формаяьно сяедоваяо бы опредеянть множество О1 как множество, находюпееся во езапмно однозначном соотвеетслзеии с множеством 2О, но нам все-таки удобнее считать, что О1 совпадает с 2О, — ведь множеством состояний конечного автомата может быть любое непустое конечное множество.
7.6. Детермивваацви иовечвых автоматов 525 Обратим внимание на то, что среди состояний нового конечного автомата есть состояние И, причем, согласно (7.8), 5~(И,а) = И для любого входного символа и. Это значит, что, попав в такое состояние, конечный автомат М1 уже его не покинет.
Вообще же любое состояние д конечного автомата, такое, что для любого входного символа а 5(д,а) = д, называют таоелотиающттм состполтепем конечного пвтоааапта. Таким образом, состояние И детерминированного конечного автомата М1 является поглощающим. Полезно заметить также, что Ю~(Я,а) = И тогда и только тогда, когда для каждого д Е Я (состояния старого конечного автомата из множества состояний Я) 6(в, а) = И, т.е. в графе М из каждого такого состояния в не выходит ни одна дуга, помеченная символом а.
Можно доказать (см. Д.7.1), что полученный по такому алгоритму конечный автомат эквивалентен исходному. ~ Пример 7.9. Детерминизируем конечный автомат, изображенный на рис. 7.14. Рмс. 7.16 Рис. 7.14 Эквивалентный конечный автомат без Л-переходов изображен на рис. 7.15. Заметим, что вершина от исчезает, так как в нее заходят только „пустые" дуги.
Чтобы детерминизировать полученный автомат, совершенно не обязательно выписывать все его 2 = 8 состояний, среди которых многие могут оказаться не достижимыми из начального состояния (ве). Чтобы получить достижимые из (де) 526 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ состояния, и только их, воспользуемся так называемым методом вытягивания. Этот метод в общем случае можно описать так. В исходном конечном автомате (без пустых дуг) определяем все множества состояний, достижимых из начального, т.е. для каждого входного символа а находим множество б(де,а). Каждое такое множество в новом автомате является состоянием, непосредственно достижимым вз начального. Для каждого из определенных состояний-множеств Ь' и каждого входного символа а находим множество ( ) б(д,а).
Все оея полученные на этом шаге состояния будут состояниями нового (детерминированного) автомата, достижимыми из начальной вершины по пути длины 2. Описанную процедуру повторяем до тех пор, пока не перестанут появляться новые состояния- множества (включая пустое!). Можно показать, что при этом получаются все такие состояния конечного автомата Мд, которые достижимы из начального состояния (дед. Для конечного автомата на рис.
7.15 имеем: бд((до),а) = (дд); бд((до),Ь) = (дд, дз); бд((дд),а) = (дд); бд((дд),Ь) = (дд); бд((дд, дз11 а) = б(дд,а) О б(дз, а) = (дд) 0 (дд1 = (дд); бд((дд дз) Ь) = б(дд, Ь) О б(дз Ь) = (дд) 0 (дд) = (дд). Так как новых состояний-множеств больше не появилось, процедура „вытягивания" на этом заканчивается, и мы получаем граф, изображенный на рис. 7.16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
