Эквивалентность состояний детерминированного автомата

Особый интерес представляет анализ множества состояний одного автомата. Если у автомата М есть состояния q_i и q_j , для которых значения функций выходов j(q_i;x_k) и j(q_j;x_k) совпадают для всех символов множества X, то есть

j(q_i; x_k) = j(q_j;x_k), (1.32)

то состояния q_i и q_j автомата М формируют неотличимую пару (q_i;q_j)Î(QÄQ).

Множество неотличимых пар (q_i;q_j)Î(QÄQ), имеющих одинаковые значения функций выходов для каждого символа x_kÎX формирует класс неотличимых состояний Q'_i. Если множество неотличимых пар содержит пары (q_i;q_j), (q_j;q_k) и (q_i;q_k), то есть выполняется условие транзитивности для отношения неотличимости, то класс неотличимых состояний формирует множество Q'_i={q_i;q_j;q_k}.

Если для неотличимой пары состояний (q_i;q_j) значения функций переходов формируют для всех символов x_kÎX также пары неотличимых состояний (y(q_i[t];x_k[t]);y(q_j[t];x_k[t])), то такие состояния q_i и q_j называют совместимыми.

Множество совместимых пар, имеющих одинаковые значения функций переходов для каждого символа x_kÎX, формирует класс совместимых состояний Q''_i. Если множество совместимых пар содержит пары (q_i;q_j), (q_j;q_k) и (q_i;q_k), то есть выполняется условие транзитивности для отношения совместимости, то класс совместимых состояний есть Q''_i={q_i;q_j;q_k}.

Если состояния q_i и q_j автомата М неотличимы и совместимы, то они эквивалентны. Поэтому класс совместимых состояний есть класс эквивалентных состояний.

Для поиска эквивалентных состояний автомата М также следует заполнить таблицу переходов пар неотличимых состояний. Левый столбец таблицы предназначен для указания пар неотличимых состояний (q_i;q_j)Î(QÄQ), которые определяют по таблице выходов для всех x_kÎX по условию j(q_i;x_k)=j(q_j;x_k). Позициями этой таблицы являются пары (y(q_i;x_k);y(q_j;x_k)), в которые переходит автомат из неотличимой пары (q_i;q_j) для каждого символа x_kÎX. Значения (y(q_i;x_k);y(q_j;x_k)) определяются по таблице переходов автомата М.

Пусть таблица переходов пар состояний одного автомата представлена таблицей 1.22, где множество пар неотличимых состояний есть (q_p;q_r), (q_r;q_s), (q_s;q_t), (q_t;q_u).

Анализ таблицы показывает, что

1) состояния q_p и q_r совместимы, т.к. при приеме каждого символа входного алфавита состояния автомат переходят в неотличимые пары состояний;

2) состояния q_s и q_t совместимы, т.к. при приеме каждого символа входного алфавита автомат переходит в одну и ту же пару неотличимых состояний;

3) состояния q_r и q_s не совместимы, т.к. при приеме символа x₂ автомат переходит в разные пары неотличимых состояний, т. е. различимы между собой по выходу;

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

Таблица 1.22.

Множество совместимых состояний, имеющих одинаковые значения функций переходов для каждого символа x_kÎX, формируют классы эквивалентных состояний. Так по таблице 1.22 формируются классы эквивалентных состояний Q''₁={q_p,q_r} и Q''₂={q_s,q_t}, каждый из которых можно заместить одним состоянием q'₁«{q_p;q_r} и q'₂«{q_s;q_t}. Множество несовместимых состояний формируют классы отличимых состояний. Например, Q''₃=q_u. Множество классов называется минимальным, если все внутренние состояния автомата принадлежат минимальному числу согласованных и отличимых классов. В данном примере минимальный автомат представляют три класса: Q''₁={q_p;q_r}, Q''₂={q_s;q_t} и Q''₃=q_u. Состояния каждого класса можно "склеить" в одно состояние q' и заполнить таблицы переходов и выходов известными значениями функций состояний соответствующего класса.

Пример 1.6. Пусть дан автомат M=áX;Y;Q;y;jñ, где X={0;1}, Y={0;1}, Q={q₁;q₂;q₃;q₄;q₅}, y и j (см. таблицу 1.23). Найти эквивалентные состояния автомата.

Множество неотличимых пар по условию j(q_i;x_k) =j(q_j;x_k) для каждой пары состояний (q_i;q_j)Î(QÄQ) есть (q₁;q₂), (q₁;q₃), (q₁;q₄), (q₂;q₃), (q₂;q₄) и (q₃;q₄).

В это множество можно включить (q₂;q₁), (q₃;q₁), (q₄;q₁), (q₃;q₂), (q₄;q₂) и (q₄;q₃). Однако, очевидно, что отношение неотличимости симметрично. Поэтому симметричные пары состояний не следует включать в таблицу переходов пар неотличимых состояний.

Множеству неотличимых пар принадлежат также (q₁;q₁), (q₂;q₂), (q₃;q₃), (q₄;q₄) и (q₅;q₅), так как отношение неотличимости рефлексивно. Такие пары не следует включать в левый столбец таблиц переходов пар неотличимых состояний, но следует помнить при анализе позиций таблицы.

Таблица 1.23.

Для формирования класса неотличимых состояний следует проверить отношение неотличимости по условиям транзитивности. Все множество неотличимых пар примера удовлетворяет этому условию. Поэтому формируется один класс неотличимых состояний Q'₁={q₁,q₂,q₃,q₄}, Для состояния q₅ нет другого состояния, формирующего неотличимую пару. Поэтому состояние q₅ формирует класс отличимых состояний Q'₂=q₅.

При этом выполняются условия Q'₁ÈQ'₂=Q и Q'₁ÇQ'₂=Æ.

Для поиска совместимых состояний построим таблицу переходов пар неотличимых состояний (см. таблицу 1.24).

Таблица 1.24.

Анализ таблицы показывает, что для входного символа "0" неотличимые пары (q₁;q₃) и (q₂;q₃) переходят в пару различимых состояний q₁ÎQ'₁ и q₅ÎQ'₂, а пара (q₃;q₄) - в пару различимых q₄ÎQ'₁ и q₅ÎQ'₂. Поэтому пары (q₁;q₃), (q₂;q₃) и (q₃;q₄) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу 1.25. Неотличимые пары, обусловливающие переход в пары различимых состояний, подчеркнуты в таблице 1.24.

Таблица 1.25.

Анализ таблицы показывает, что для входного символа "1" неотличимые пары (q₁;q₂) и (q₂;q₄) переходят в удаленную на предыдущем этапе неотличимую пару (q₂;q₃). Поэтому пары (q₁;q₂) и (q₂;q₄) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу 1.26. Неотличимые пары, обусловливающие переход в пары различимых состояний, подчеркнуты в таблице 1.25.

Таблица 1.26.

Анализ таблицы показывает, что состояния q₁ и q₄ формируют класс неотличимых и совместимых состояний Q''_i={q₁,q₄}, то есть они эквивалентны.

Контрольные вопросы и задачи.

1) Начертить граф и найти эквивалентные состояния автомата, описанного таблицей:

2) Начертить граф и найти эквивалентные состояния автомата, описанного таблицей:

3) Начертить граф и найти эквивалентные состояния автомата, описанного таблицей:

Дата добавления: 2015-07-26; просмотров: 200; Нарушение авторских прав

Мы поможем в написании ваших работ!