нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
 Скачать 0.65 Mb.
|
2.7. Процедура минимизации частичного автомата2.7.1. Совместимые состоянияОпределение. Состояние называется совместимым по выходу с состоянием , если для всех . В этом случае пишется .Если состояния не совместимы по выходу, то пишут Например для автомата Таблица 20
, т.е. отношение не транзитивно Определение. Состояния и являются совместимыми, если для всех допустимых как для , так и для , имеем , в этом случае используется запись .Если и совместимы не для всех , то пишется . Если и совместимы для всех строк фиксированной длины k, то они называются k – совместимыми и обозначаются Таким образом, если автомат, начав работу в состоянии или , для любой входной строки , дает одинаковые выходы в тех позициях, которые определены. Тогда состояния и совместимы и их можно склеить в одно состояние. Эта операция не изменит выходы в определенных позициях и даст безразличный выход в тех позициях, которые ранее давали безразличные выходы, хотя бы для одного из состояний. Таким образом, новый выход будет покрывать оба старых. Обозначается новое состояние через s. Тогда для всех , допустимых для , и для всех , допустимых для . Отношение совместимости указывает возможность комбинирования состояний для их склеивания, но не указывает точного способа склеивания этих состояний. 2.7.2. Техника определения совместимых состояний Пусть требуется определить отношения совместимости состояний для не полностью описанного автомата, заданного таблицей состояний. Таблица 21
Сначала следует определить т.к. оно является подмножеством . содержит одну пару (2,5). Все остальные пары Составим таблицу совместимости, строки которой нумеруются элементами , а столбцы входными символами Таблица 22
На пересечении столбцы и строки указаны пары состояний, в которые переводит пару . Например , переводит в и в ; Поэтому на пересечении (1,2) и стоит (2,3). Если одно или оба из следующих состояний безразличны, или исходная пара переходит в одно и то же состояние, то в соответствующей позиции ставится прочерк. Предположим, что некоторый элемент множества переводится в элемент множества некоторой входной строкой. Тогда первоначальный элемент лежит в . Следовательно, после применения этого входа для получившийся пары из получаются разные выходы, и следовательно, будут разные выходы для первоначальной пары. Например, переводит (1,3) в (2,5), а (2,5) , т.к. эти состояния 2 и 5 дают разные выходы при входе . Поэтому состояния (1,3) дадут разные выходы при входе . Далее составляем список элементов множества (т.к. отношение совместимости рефлексивно и симметрично, то выписываются пары . Затем добавляются пары, которые некоторым символом переводятся в только что полученные пары. Эти пары различаются подходящим входом длины 3. В нашем случае на этом шаге добавляется пары (1,5) и т.д. В результате график отношений имеет вид: Процедуры заканчиваются тогда, когда новые пары перестают возникать. Это произойдет не позже чем через шагов, где число состояний автоматы. Последнее полученное отношение будет и, следовательно, отношение содержит остальные пары, т.е. 2.7.3. Построение минимального автоматаСовместимым классом называется множества внутренних состояний таких, что для всех . Максимальным совместимым классом называется совместимый класс, не содержащийся в качестве собственного подмножества в другом совместимом классе. Полное множество максимальных совместимых классов есть список самых больших подмножеств состояний, каждое из которых можно склеить в одно состояние. В нашем случае максимально совместимые классы это (1,2), (1,4), (2,3) и (3,4,5,). Определение. Некоторое множество совместимых классов называется согласованным, если для любого класса из этого множества и любых его элементов внутренние состояния принадлежат подходящему совместимому классу для любого символа . Определение. Некоторое множество совместимых классов называется замкнутым, если всякое внутренне состояние автомата принадлежит, хотя бы одному из этих классов Теорема. Пусть задано замкнутое согласованное множество совместимых классов для автомата M, тогда существует автомат , покрывающий автомат М, состояния которого получаются склеиванием всех состояний М, содержащихся в одном совместимом классе из данного множества. Если исходное замкнутое согласованное множество содержит наименьшее число совместимых классов, то автомат , покрывающий автомат М, и полученный склеиванием всех состояний каждого класса в одно состояние, будет минимальным. Рассмотрим автомат, анализируемый ранее. Одно из возможных предложений состоит в разбиении на классы эквивалентности и , которое привело бы к автомату с двумя состояниями. Однако , это значит, что данное предложение не годится, поскольку указанное разбиение не согласованно. Никакая другая пара совместимых классов не покрывает всё множество состояний. Поэтому следует рассмотреть разбиение на 3 класса. Такое согласованное разбиение из трех классов существует. . Соответствующий минимальный автомат существует. Рассмотрим другой пример таблицы состояний автомата Таблица 23
все остальные Составим таблицу совместимости Таблица 24
Максимально совместимыми классами являются {1,2,4,5} и {3} Это разбиение является согласованным, следовательно, соответствующий автомат выглядит следующим образом Таблица 25
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||