Получение минимального автомата

Приведённые автоматы.

Алгоритм составления списка достижимых состояний.

Для любого данного автомата – составить список достижимых состояний.

1) Начать список в начальном состоянии.

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

Если эта процедура перестаёт давать новые состояния, то все достижимые состояния получены, а все остальные можно удалить из автомата. Число шагов процедуры ограничено числом состояний данного автомата.

S0-> S1 и S5; S1 -> S2 и S7; S5-> S3 и S1. Переходов в другие состояния нет => S4, S6 и S8 - недостижимы, и автомат можно сократить.

S0 S1 S2 S3 S4 S5 S7	S1 S2 S2 S5 S5 S3 S0	S5 S7 S5 S7 S6 S1 S1

Определение: Автомат приведённый, если он не содержит недостижим состояний и никакие 2 его состояний не эквивалентны друг другу.

Замечание: Если автомат не приведённый, то можно получить эквивалентный ему автомат с меньшим числом состояний, как раннее было показано.

Осуществляя приведение различными способами или начиная с разных эквивалентных автоматов, можно предположить, что полученные приведённые автоматы окажутся разными. Однако, они фактически одинаковы во всех отношениях, за исключением имён, которыми названы их состояния.

Значит, какой бы распознаватель ни был выбран для некоторой проблемы распознавания и каким бы образом ни происходило бы приведение его состояний, можно построить только 1 приведённый автомат. Этот автомат называется минимальным автоматом.

Метод проверки эквивалентности состояний, рассмотренный выше, использовать для приведения автоматов не удобно, т.к. он позволяет обработать только 2 состояния. Рассмотрим другой, более практичный метод – «метод разбиения». Он заключается в разбиении множества состояний на непересекающиеся подмножества, такие что не эквивалентные состояния попадают в разные блоки.

Сначала состояния разбиваются на 2 блока: один содержит допускающие состояния, другой – отвергающие. В нашем примере начальное разбиение Р₀ = ({1, 2, 3, 4}, {5, 6, 7})

{1, 2, 3, 4} – отвергающие; {5, 6, 7} – допускающие

Ни одно состояние из первого блока не эквивалентно никакому состоянию (ни одному) второго блока, т.к. нарушаются условия подобия.

	y	z

Теперь посмотрим, что происходит с состоянием первого блока под действием входного символа а. Состояния 3 и 4 переходят в состояния, принадлежащие первому блоку (1 и 4), тогда как состояния 1 и 2 переходят в состояний, принадлежащие второму блоку (6 и 7). Это означает, что для любого состояния из множества {1, 2} и любого из {3, 4} соответствующие состояния – приемники по входу а будут не эквивалентны. Это позволяет произвести новое разбиение P₁ =({1,2}, {3,4}, {5, 6, 7}), причем состояния из разных блоков всегда неэквивалентны, причём получили состояния Р₁ и Р₀, разбивая блок {2,3,4} относительно входа а. теперь попытаемся найти такой входной символ и такой блок в Р₁, чтобы его можно было разбить относительно этого входного символа и получить тем самым новое разбиение. Для этого разбиение также будет выполняться свойство неэквивалентности состояний, принадлежащих разным блокам. Повторяем процесс пока дальнейшее разбиение становится невозможным. Т.к. мы не остановили порядок, в котором входные символы и блоки проверяются на возможность разбиения, последовательность разбиений можно порождать многими способами. Последнее разбиение будем одним и тем же во всех случаях. В нашем примере, разбивая блок {3,4} из Р₁ относительно а и получаем: P₂ =({1,2}, {3}, {4}, {5, 6, 7}). Далее разбиваем {5, 6, 7} из P₂ относительно а или b, получаем: P₃ =({1,2}, {3}, {4}, {5}, {6, 7}). P₃ – не допускает дальнейшего разбиения. Все состояния блока {1,2} переходят относительно а в состояния блока {6,7}, а относительно b в {3}. Аналогично блок {6,7} переходит в {4} и {1,2} относительно а и b соответственно. Оставшееся блоки имеют по одному элементу, по этому автоматически исключают дальнейшее разбиение.

Когда процедура закончена, состояния внутри каждого блока эквивалентны. В примере: 1~2 и 6~7. Блоки последнего разбиения можно использовать для построения нового автомата, который эквивалентен исходному и не содержит эквивалентных состояний.

	a	b
{1,2} {3} {4} {5} {6,7}	{6,7} {1,2} {4} {6,7} {4}	{3} {5} {6,7} {3} {1,2}

Множество состояний нового автомата – это множество блоков последнего разбиения. Переходы нового автомата получены из старого, прослеживая переходы из блока в блок, для каждого входного символа. Автомат не имеет недостижимых состояний и является, поэтому минимальным. В общем случае процедура разбиения должна сопровождается выбрасыванием недостижимых состояний в целях получения минимального автомата. Не имеет значения, какая из двух процедур выполняется первой.

Дата добавления: 2014-01-11