Минимизация конечных автоматов. Минимизация конечных автоматов — копия. 1 минимизация конечных автоматов 5 пример минимизации конечного автомата 8
 Скачать 168.03 Kb.
|
СодержаниеВВЕДЕНИЕ 2 ГЛАВА 1 5 1.1. МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ 5 1.2. ПРИМЕР МИНИМИЗАЦИИ КОНЕЧНОГО АВТОМАТА 8 ГЛАВА 2 10 2.1. МИНИМИЗАЦИЯ НЕПОЛНЫХ КОНЕЧНЫХ АВТОМАТОВ 10 2.2.ПРЕДЕЛЬНЫЕ СЛУЧАИ МИНИМИЗАЦИИ 12 ЗАКЛЮЧЕНИЕ 13 СПИСОК ЛИТЕРАТУРЫ 13 ВВЕДЕНИЕАвтоматы — вычислительные машины, представленные в виде математических моделей. Абстрактный дискретный автомат – модель дискретного устройства, имеющего один вход, два выхода и в каждый момент времени находящегося в одном состоянии из множества возможных. Конечный автомат — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно. Теория конечных автоматов практически широко используется в: синтаксических и лексических анализаторах; тестировании программного обеспечения на основе моделей. Существуют различные способы задания алгоритма функционирования конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки элементов некоторых множеств:  Где: V – входной алфавит1, из которого формируются входные слова2, воспринимаемые конечным автоматом; Q – множество внутренних состояний; q0 – начальное состояние (q0 принадлежит Q); F – множество заключительных или конечных состояний (F является подмножеством Q)  - функция переходов, определённая, как отображение  значение функции переходов есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке символов, обычно обозначаемой буквой -  При анализе конечного автомата принято полагать, что конечный автомат начинает работу в некотором начальном состоянии q0, последовательно получает по одному символу из входного слова. Считанный символ3 может перевести автомат в новое состояние или не перевести в новое состояние в соответствии с функцией переходов. Получая входную цепочку символов x и делая переходы из состояния в состояние, автомат после получения последнего символа входного слова окажется в некотором состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил слово x. Диаграмма состояний
Детерминированный конечный автомат – такой автомат, в котором нет предложений, не содержащих ни одного символа, из любого состояния по любому символу возможен переход не более, чем в одно состояние. Неполный конечный автомат (недетерминированный конечный автомат) – это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой4. Имеет единственную последовательность состояний во время работы. Недетерминированность автоматов может достигаться двумя способами: либо могут существовать переходы из состояния в состояние, вызываемые пустой цепочкой символов, то есть самопроизвольные переходы без внешних воздействий; либо из одного состояния КА может переходить в разные состояния под воздействием одного и того же символа. Так для чего же нужна минимизация автоматов в принципе? Под минимизацией числа внутренних состояний автомата понимается процесс, целью которого является получение автомата имеющего минимальное число внутренних состояний среди всех автоматов, реализующих заданные условия работы. Таким образом целью минимизации является сделать минимальным количество состояний, при этом сохранив заданные функции выхода. ГЛАВА 11.1. МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВТеорема о детерминированности: Для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат. В силу теоремы о детерминизации можно считать, что исходный конечный автомат M = (V, Q, q0, F,  ) является детерминированным.Также будем предполагать, что в исходном конечном автомате нет состояний, которые не достижимы из начального состояния. Это предположение мотивировано тем, что если в M0 существуют состояния, не достижимые из начального, то их можно найти и удалить со всеми инцидентными5 им дугами. На множестве состояний автомата M зададим семейство отношений эквивалентности следующим образом: 0 – эквивстентностъ: для произвольных состояний q1 и q2 полагаем, что q1 ≡0 q2 тогда и только тогда, когда они оба являются заключительными или оба не являются заключительными; k-эквивалентность: при k ≥ 1 полагаем, что q1 ≡k q2 тогда и только тогда, когда q1 ≡k-1 q2, т.е. состояния k1 и q2(k-1) – эквивалентны, и для любого входного символа a состояния δ(q1, a) и δ(q2, a) также (k-1) – эквивалентны. Напомним, что функция переходов детерминированного конечного автомата определена как отображение δ: Q × V Q Чтобы понять смысл отношения k-эквивалентности, обратимся к рисунку 1.  Рисунок 1 На этом рисунке q1 и q2 — (k-1)-эквивалентные состояния, т.е. они принадлежат одному и тому же классу (k-1)-эквивалентности C1. Эти состояния, согласно данному выше определению, станут k-эквивалентными, если для любого входного символа a состояния δ(q1, a) и δ(q2, a) также являются (k-1)-эквивалентными, содержащимися в некотором классе (k-1)-эквивалентности C2 (возможно, что C1 = C2). Можно сказать, что (k-1)-эквивалентные состояния будут также и k-эквивалентными, если переход из них по любому входному символу "сохраняет" (k-1)-эквивалентность состояний. То есть состояния, в которые конечный автомат переходит из (k-1)-эквивалентных состояний снова окажутся (k-1)-эквивалентными. Если же найдется хотя бы один входной символ а, такой, что состояния δ(q1, a) и δ(q2, a) окажутся в разных классах (к-1)-эквивалентности (рисунок 2),  Рисунок 2 то состояния q1 и q2 уже не будут k-эквивалентными. Таким образом, для любого k ≥ 0 отношение эквивалентности ≡k+1 включается в отношение ≡k => каждый класс k-эквивалентности или разбивается на несколько попарно непересекающихся классов (k+1)-эквивалентности, или, если все его состояния остаются (k+1)-эквивалентными, не изменяется. Это значит, что разбиение множества состояний на классы (k+1)-эквивалентности является, не более "крупным". То есть содержит не меньше классов эквивалентности, чем разбиение на классы k-эквивалентности. Минимизация конечного автомата состоит в последовательном "измельчении" разбиения множества Q на классы эквивалентности до тех пор, пока не получится разбиение, которое уже нельзя измельчить. Получаем: указанные выше отношения эквивалентности строятся до такого наименьшего k, что отношение ≡k совпадет с отношением ≡k+1. Это отношение и определяет самое мелкое разбиение множества состояний. Обозначим его просто ≡. Тогда минимальный конечный автомат M = (V', Q', q'0, F', δ'), т.е. автомат с наименьшим числом состояний, эквивалентный исходному, определяется следующим образом: V' = V, Q' = Q/≡ , q'0 = [q0], F' = {[f]: f ∈ F}, ( Ɐa ∈ V)( Ɐq ∈ Q) δ([q], a) = [δ(q, a)], Где через [q] обозначен класс эквивалентности состояния q по отношению ≡. Резюмируем полученные результаты: для произвольного конечного автомата может быть построен эквивалентный ему конечный автомат с наименьшим числом состояний. Вытекающий из этой теоремы алгоритм минимизации может быть описан так: строим эквивалентный исходному детерминированный конечный автомат; если в полученном конечном автомате остались состояния, не достижимые из начальной вершины, удаляем; к полученному конечному автомату применяем изложенный выше алгоритм построения разбиения множества состояний на классы эквивалентности по отношению ≡ и строим минимальный конечный автомат M', как описано выше. 1.2. ПРИМЕР МИНИМИЗАЦИИ КОНЕЧНОГО АВТОМАТАМинимизируем конечный автомат, изображённый на рисунке 3:  Рисунок 3 Введем новые обозначения для состояний автомата: { q0 } = s0, { q0, q1 } = s1, { q0, q2 } = s2, { q0, q1, q3 } = s3, { q0, q2, q3 } = s4, { q0, q3 } = s5. Полученный автомат изображен на рисунке 4:  Рисунок 4 Запишем разбиение множества состояний автомата для отношения: ≡0: { s0, s1, s2 }, , { s3, s4, s5 }. Так как состояния δ(s2, 0) = s0 и δ(s2, 1) = s3 не являются 0-эквивалентными состояниями, то в разбиении для 1-эквивалентности они "разойдутся" по разным классам; разбиение, определяемое отношением ≡1, будет иметь вид: { s0, s1 }, { s2 }, { s3, s4, s5 }. Далее, при переходе к 2-эквивалентности придется "развести" состояния s0 и s1. Поскольку для всех состояний из множества {s3, s4, s5} конечный автомат переходит в одно из этих же состояний, то разбиение на классы 2-эквивалентности и есть искомое "мельчайшее" разбиение: { s0 }, { s1 }, { s2 }, { s3, s4, s5 }. На рисунке 5 приведен граф минимального конечного автомата:  Рисунок 5 ГЛАВА 2 2.1. МИНИМИЗАЦИЯ НЕПОЛНЫХ КОНЕЧНЫХ АВТОМАТОВ На практике встречаются случаи, когда не каждый символ входного алфавита может быть подан на автомат, находящийся в некотором внутреннем состоянии q (ограничения на входе), или его выходы при некоторых входных воздействиях не представляют интереса или вообще не существуют (неопределенность выходов). Такие автоматы называются неполными. На рисунке 6 приведен пример неполного конечного автомата.  Рисунок 6 Квазиэквивалентный автомат – это такой автомат, который по отношению к допустимым для исходного автомата входным последовательностям ведет себя на выходах так же, как и исходный автомат, но имеет меньшее число состояний. Такой автомат называют сокращенной формой исходного. Отношение квазиэквивалентности рефлексивно и транзитивно, однако не симметрично. Исходя из этого говорят, что сокращенная форма неполного автомата включает исходный неполный автомат. Задача минимизации неполного автомата сводится к поиску квазиэквивалентного автомата, который имеет наименьшее число состояний. Сначала определяется отношение совместимости на множестве состояний Q = { q1, q2, … , qr } исходного автомата. Совместимыми являются такие состояния qi и qj, для которых любая допустимая для этих состояний входная последовательность не порождает различных выходов при начальных состояниях qi и qj автомата. Отношение совместимости рефлексивно и симметрично, но не обязательно транзитивно. Следовательно, совместимость является отношением толерантности. Все совместимые между собой состояния объединяются в классы толерантности Q'0, Q'1, …, Q'm, которые образуют некоторое покрытие множества состояний Q. Метод определения совместимых состояний аналогичен уже описанному методу для эквивалентных состояний. Из определения совместимости и способа получения классов толерантности следует, что при воздействии любого разрешенного входного символа автомат из совместимых состояний переходит в одно и то же или в совместимые состояния, а выходы (если они определены) при этом будут одинаковы. Таким образом, исходный автомат можно представить в виде квазиэквивалентного ему автомата, в котором классы толерантности Q'0, Q'1, …, Q'm соответствуют состояния q'0, q'1, …, q'm. Но этот автомат не обязательно будет минимальным. Для достижения минимальной формы автомата необходимо отобрать минимум классов толерантности, образующих покрытие исходного множества состояний Q. В то же время отобранные классы толерантности должны включать множества состояний, следующих за состояниями при всех разрешенных входных воздействиях. Дальнейшие упрощения относятся к структуре множеств, образующих минимальное покрытие Q. Из отобранных классов толерантности следует отключить некоторые состояния, так, что полученные подмножества будут удовлетворять изложенным выше требованиям. ПРЕДЕЛЬНЫЕ СЛУЧАИ МИНИМИЗАЦИИПроцедура минимизации имеет два крайних случая: Все состояния исходного автомата окажутся эквивалентными, следовательно в минимизированном автомате останется лишь одно состояние; Исходный автомат уже минимален, итоговый автомат состоит из одноэлементных классов эквивалентности. Рассмотрим в качестве примера первого случая конечный автомат и его минимизация, допускающие язык, который обозначен регулярным выражением (a*b*)*. Приведенный пример проиллюстрирован на Рисунке 7.  После процедуры минимизации получаем детерминированный автомат, все состояния которого заключительные. Следовательно, минимальный автомат состоит из одной вершины и допускает язык (a + b)*. Получается, что регулярные выражения (a*b*)* и (a + b)* эквивалентны в алфавите {a, b}. ЗАКЛЮЧЕНИЕВ данной работе подробно изучены полные и неполные конечные автоматы, понятия эквивалентности и совместимости состояний, методы минимизации автоматов. Приведены примеры минимизации конечных автоматов. СПИСОК ЛИТЕРАТУРЫКарпов Ю.Г. Теория автоматов (Учебное издание для вузов). Издательство «Питер», 2003г Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. 2007г ISBN: 978-5-9556-0062-8 Дехтярь М. И. Лекции по дискретной математике. Учебное пособие. 2007г ISBN: 978-5-94774-714-0 1 Алфавит – конечный набор различных символов 2 Слово — строка символов, создаваемая через конкатенацию (соединение). 3 Символ — любой атомарный (то есть неделимый более без потери смысла) блок данных, который может производить эффект на машину. Чаще всего символ — это буква некоего формального языка. 4 Строка – последовательность символов. 5 Инцидентность - когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро. | |||||||||||||||||||||||||||||||