Минимизация автомата

Треугольная таблица пар состояний Таблица 6

q2

X

q4

X

X

q5

X

X

X

q6

X

X

X

q8,q9

q7,10

X

X

X

X

X

q8

X

X

X

X

X

X

q9

X

q5,q0,19

X

X

X

X

X

q11

X

X

X

X

X

X

X

X

q12

X

q5,q13

X

X

X

X

X

q0,19,q13

X

q13

X

X

X

X

X

X

X

X

X

X

q15

X

q5,q16

X

X

X

X

X

q0,19,q16

X

q13,q16

X

q16

X

X

X

X

X

X

X

X

X

X

↔

X

q17

X

X

X

X

X

X

X

X

X

X

X

X

X

q18

X

X

X

X

X

X

X

X

X

X

↔

X

↔

X

q1,3

q2

q4

q5

q6

q7,10

q8

q9

q11

q12

q13

q15

q16

q17

 

Получаем 4 пары эквивалентных состояний: (q₁₂, q₁₅), (q₁₃, q₁₆), (q₁₃, q₁₈), (q₁₆, q₁₈).

Эти пары состояний образуют два класса эквивалентности: {q₁₂, q₁₅}, {q₁₃, q₁₆, q₁₈}.

Все другие состояния, не вошедшие в эти классы эквивалентности, эквивалентны сами себе и образуют индивидуальные классы. В нашем примере к перечисленным двум классам эквивалентности следует добавить еще 16 классов:

{q₀}, {q_0,19}, {q_1,3},{q₂}, {q₄}, {q₅}, {q₆}, {q_7,10}, {q₈}, {q₉}, {q₁₁}, {q_14,19}, {q₁₇}, {q₁₉}, {q₂₀}, {q₂₁}.

Поставим в соответствие классам эквивалентности состояния минимального автомата (r­_n):

r₀ = {q₀},

r₁ = {q_0,19},

r₂ = {q_1,3},

r₃ = {q₂},

r₄ = {q₄},

r₅ = {q₅},

r₆ = {q₆},

r₇ = {q_7,10},

r₈ = {q₈},

r₉ = {q₉},

r₁₀ = {q₁₁},

r₁₁ = {q₁₂, q₁₅},

r₁₂ = {q₁₃, q₁₆, q₁₈},

r₁₃ = {q_14,19},

r₁₄ = {q₁₇},

r₁₅ = {q₁₉},

r₁₆ = {q₂₀},

r₁₇ = {q₂₁}.

r₁₇ – состояние «Ошибка».

Таблица переходов минимального автомата Таблица 7

	x0	x1	x2	x3	x4	x5	x6	x7	x8
r0		r2					r7
r1		r2					r7		r16
r2	r3							r4
r3							r5
r4						r6
r5			r8			r15
r6			r9			r15
r7	r10		r9			r13		r14
r8					r0		r15
r9							r1
r10					r11
r11							r12
r12	r15
r13					r11				r16
r14				r12
r15									r16

 

r13

r16

r10

r11

r12

r9

r1

r4

r6

r15

r8

r5

r3

r2

r7

r0

x1

x0

x7

x6

x0

x1

x4

x5

x3

x6

x5

x5

x2

x6

x8

x0

x6

x4

x8

x5

x6

x8

x4

x6

x2

Рисунок 3. Граф переходов минимального автомата.

 

 

 

Использование сетей Петри при переходе от грамматики к минимальному автомату

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

Рисунок 4. Сеть Петри, соответствующая грамматике G’.

 

r13

r16

r10

r11

r12

r9

r1

r4

r6

r15

r8

r5

r3

r2

r7

r0

Рисунок 5. Сеть Петри, соответствующая минимальному автомату.

Структурный синтез автомата

Автомат реализуется как синхронный автомат. Он имеет тактовый генератор, и переход в новое состояние осуществляется по тактовому импульсу. Запоминающее устройство автомата может быть реализовано с помощью нескольких видов триггеров.

Дешифратор

Комбинационная схема

Регистр 1

Регистр 2

Функции возбуждения автомата Таблица 7

Сост	Сост	Код сост.	Функции возбуждения
D-триггеров
z1	z2	z3	z4	D1	D2	D3	D4
q0	r0					x6	x6+x1	x6
q0,19	r1					-x1	x1+x6	x6
q1,3	r2					x0	-x7	x7
q2	r3						x6	-x6
q4	r4						x5
q5	r5					-x3	x5	-x3	x3+x5
q6	r6					x2+x5	-x2	-x2	x2+x5
q7,10	r7					-x0	-x5*-x2	-x5*-x2	x0+x5+x2
q8	r8								-x4
q9	r9								-x6
q11	r10					x4
q12,15	r11					-x6	-x6	x6
q13,16,18	r12					x0	x0
q14,19	r13					*	*	*	*
q19	r15					*	*	*	*

 

 

Выводы

В ходе выполнения расчётно-графической работы были выполнены все поставленные задачи.

Были изучены некоторые способы задания языков грамматиками и распознающими автоматами. После этого был построен конечный автомат, распознающий язык, заданный в индивидуальном задании.