Минимизация абстрактных автоматов

Певзнер Д.Я., гр. И491

Домашняя работа №18 «Минимизация абстрактных автоматов»

Вариант 6

Таблица переходов δ(q,x)

Таблица выходов λ(q,x)

1. По таблице выходов построим разбиение π₁ на классы одноэквивалентных состояний.

π₁ = {В1,В2,В3,В4};  В1 = {q0,q4,q5,q8,q12,q13};  B2 = {q1,q7,q9,q15};  В3 = {q2,q6,q10,q14}; B4 = {q3,q11}

По таблице переходов автомата построим таблицу разбиения π₁, в которой состояния автомата заменяем соответствующими классами эквивалентности.

2. По таблице разбиений π₁ строим разбиение π₂ на классы 2-эквивалентных состояний.

π₂ = {C1,C2,C3,C4,C5,C6,C7,C8};  C1 = {q0,q8};  C2 = {q4,q12};  C3 = {q5,q13};  C4 = {q1,q9};  C5 = {q7,q15}; 

C6 = {q2,q10};  C7 = {q6,q14};  C8 = {q3,q11};

По изначальной таблице переходов строим таблицу разбиения π₂ состояний автомата.

3. По таблице разбиений π₂ строим разбиение π₃ на классы 3-эквивалентных состояний. Оно совпадает с разбиением π₂, следовательно, разбиение π₃ есть разбиение множества состояний автомата Мили на классы эквивалентных между собой состояний. Выберем из каждого класса эквивалентности по одному состоянию: Q’ = {q0,q1,q2,q3,q4,q5,q6,q7}. Теперь определим минимальный автомат Мили:

Таблица переходов δ(q,x)

Таблица выходов λ(q,x)