Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Lektsii_YaPiMT_ispravlennoe (2).docx
Скачиваний:
1
Добавлен:
01.03.2025
Размер:
343 Кб
Скачать
☆

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

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

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

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

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

y

z

1

2

3

4

5

6

7

6

7

1

4

7

4

4

3

3

5

6

3

1

2

0

0

0

0

1

1

1

Теперь посмотрим, что происходит с состоянием первого блока под действием входного символа а. Состояния 3 и 4 переходят в состояния, принадлежащие первому блоку (1 и 4), тогда как состояния 1 и 2 переходят в состояний, принадлежащие второму блоку ( 6 и 7). Это означает, что для любого состояния из множества {1, 2} и любого из {3, 4} соответствующие состояния – приемники по входу а будут не эквивалентны. Это позволяет произвести новое разбиение P1=({1,2}, {3,4}, {5, 6, 7}), причем состояния из разных блоков всегда неэквивалентны, причём получили состояния Р1 и Р0, разбивая блок {2,3,4} относительно входа а. теперь попытаемся найти такой входной символ и такой блок в Р1, чтобы его можно было разбить относительно этого входного символа и получить тем самым новое разбиение. Для этого разбиение также будет выполняться свойство неэквивалентности состояний, принадлежащих разным блокам. Повторяем процесс пока дальнейшее разбиение становится невозможным. Т.к. мы не остановили порядок, в котором входные символы и блоки проверяются на возможность разбиения, последовательность разбиений можно порождать многими способами. Последнее разбиение будем одним и тем же во всех случаях. В нашем примере, разбивая блок {3,4} из Р1 относительно а и получаем: P2=({1,2}, {3}, {4}, {5, 6, 7}). Далее разбиваем {5, 6, 7} из P2 относительно а или b, получаем: P3=({1,2}, {3}, {4}, {5}, {6, 7}). P3 – не допускает дальнейшего разбиения. Все состояния блока {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}

0

0

0

1

1

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]