Пособие ДМ2

строк фиксированной длины к, то они называются к совместимыми и обозначаются Таким образом, если автомат, начав работу в состоянии

или , для любой входной строки̅ дает одинаковые выходы в тех позициях, которые определены. Тогда состояния и совместимы и их можно склеить в одно состояние. Эта операция не изменит выходы в определенных позициях и дает безразличный выход в тех позициях, которые ранеедавали безразличны выходы, хотя бы для одного из состояний. Таким образом, новый выход будет покрывать оба старых. Обозначается

комбинирования состояний для их склеивания, но не указывает точного способа склеиваниясостояний.

2.7.2. Техника определения совместимых состояний.

Пусть требуется определить отношения совместимости

Составим таблицу совместимости, строки которой нумеруются элементами , а столбцы входными символами

следующих состояний безразличны, или исходная пара переходит в одно и то же состояние, то в соответствующей позиции ставится прочерк.

Предположим, что некоторый элемент множества

переводится в элемент множества

некоторой входной строкой. Тогда первоначальный элемент лежит в . Следовательно после применения этого входа для получившийся пары из получаются разные выходы, и следовательно будут вы-

ставляем список элементов множества

.(т.к. отношение совместимости рефлексивно и симметрично, то выписываются пары Затем добавляются пары, которые некоторым символом

переводятся в только что полученные пары. Эти пары различаются подходящим входом длины 3. В нашем случае на этом шаге добавляется пары (1,5) и т.д. В результате график отношений имеет вид:

Процедуры заканчиваются тогда, когда новые пары перестают возникать. Это произойдет не позже чем через

совместимый класс, не содержащийся в качестве собственного подмножества в другом совместимом классе. Полное множество максимальных совместимых классов есть список самых больших подмножеств состояний, каждое можно склеить в одно состояние. В нашем случае максимально совместимы классы (1,2), (1,4),(2,3) и

(3,4,5,).

Определение. Некоторое множество совместимых классов называется согласованным, если для любого класса

из этого множества и любых его элементов

вола .

Определение. Некоторое множество совместимых классов называется замкнутым, если всякое внутренне состояние автомата принадлежит хотя бы одному из этих классов Теорема. Пусть задано замкнутое согласованное множе-

ство совместимых классов для автомата M,тогда суще-

ствует автомат ̅, покрывающий автомат М, состояния которого получаются склеиванием всех состояний М, содержащихся в одном совместимом из данного множества.

Если исходное замкнутое согласованное множество содержит наименьшее число совместимых классов, то автомат ̅, покрывающий автомат М, и полученный склеиванием всех состояний каждого класса в одно состояние, будет минимальным.

Рассмотрим автомат, анализируемый ранее. Одно из возможных предложений состоит в разбиении на классы

предложение не годится, поскольку указанное разбиение не согласованно. Никакая другая пара совместимых классов не покрывает всё множество состояний. Поэтому следует рассмотреть разбиение на 3 класса. Такое согласованное разбиение из трех классов существует.

Соответствующий

минимальный автомат.

Рассмотрим другой пример таблицы состояний автомата

все остальные Составим таблицу совместимости

Максимально совместимыми классами являются

{1,2,4,5} и {3}

Это разбиение является согласованным, следовательно, соответствующий автомат выглядит следующим образом

Прямое произведение нечетких множеств

Пример

представляет собой квадратную

( ) ( )

Носителем нечеткого отношения R называется обычное отношение такое, что

|