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

Страницы работы

1 страница (Word-файл)

Содержание работы

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

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

Вариант 6

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

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q13

q14

q15

x0

q0

q10

q2

q0

q0

q5

q7

q7

q8

q10

q2

q8

q8

q13

q15

q7

x1

q8

q9

q11

q3

q0

q14

q6

q0

q0

q1

q11

q3

q0

q6

q14

q8

x2

q5

q2

q2

q4

q12

q5

q15

q7

q13

q2

q2

q4

q4

q5

q7

q7

x3

q9

q1

q3

q11

q4

q6

q6

q12

q9

q1

q3

q3

q4

q6

q6

q12

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

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q13

q14

q15

x0

y0

y1

y1

y0

y0

y0

y1

y1

y0

y1

y1

y0

y0

y0

y1

y1

x1

y0

y0

y1

y1

y0

y0

y1

y0

y0

y0

y1

y1

y0

y0

y1

y0

x2

y0

y1

y1

y0

y0

y0

y1

y1

y0

y1

y1

y0

y0

y0

y1

y1

x3

y0

y0

y1

y1

y0

y0

y1

y0

y0

y0

y1

y1

y0

y0

y1

y0

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

π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}

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

Х

B1

B2

B3

B4

q0

q4

q5

q8

q12

q13

q1

q7

q9

q15

q2

q6

q10

q14

q3

q11

x0

B1

B1

B1

B1

B1

B1

B3

B2

B3

B2

B3

B2

B3

B2

B1

B1

x1

B1

B1

B3

B1

B1

B3

B2

B1

B2

B1

B4

B3

B4

B3

B4

B4

x2

B1

B1

B1

B1

B1

B1

B3

B2

B3

B2

B3

B2

B3

B2

B1

B1

x3

B2

B1

B3

B2

B1

B3

B2

B1

B2

B1

B4

B3

B4

B3

B4

B4

2. По таблице разбиений π1 строим разбиение π2 на классы 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};

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

Х

C1

C2

C3

C4

C5

C6

C7

C8

q0

q8

q4

q12

q5

q13

q1

q9

q7

q15

q2

q10

q6

q14

q3

q11

x0

C1

C1

C1

C1

C3

C3

C6

C6

C5

C5

C6

C6

C5

C5

C1

C1

x1

C1

C1

C1

C1

C7

C7

C4

C4

C1

C1

C8

C8

C7

C7

C8

C8

x2

C3

C3

C2

C2

C3

C3

C6

C6

C5

C5

C6

C6

C5

C5

C2

C2

x3

C4

C4

C2

C2

C7

C7

C4

C4

C2

C2

C8

C8

C7

C7

C8

C8

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


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

q0

q1

q2

q3

q4

q5

q6

q7

x0

q0

q2

q2

q0

q0

q5

q7

q7

x1

q0

q1

q3

q3

q0

q6

q6

q0

x2

q5

q2

q2

q4

q4

q5

q7

q7

x3

q1

q1

q3

q3

q4

q6

q6

q4

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



q0

q1

q2

q3

q4

q5

q6

q7

x0

y0

y1

y1

y0

y0

y0

y1

y1

x1

y0

y0

y1

y1

y0

y0

y1

y0

x2

y0

y1

y1

y0

y0

y0

y1

y1

x3

y0

y0

y1

y1

y0

y0

y1

y0

Похожие материалы

Информация о работе