spoPresentation2

Минимизация КА

Минимизация – это построение эквивалентного КА с меньшим числом состояний

устранение недостижимых состояний

объединение эквивалентных состояний

Состояние q Q КА M(Q,V,G,q0,F) недостижимое, если Z V+ невозможен

переход КА из начального состояния в состояние q.

161

Устранение недостижимых состояний КА

Дано: КА M(Q,V,G,q0,F), задающий язык L (М)

Получить: эквивалентный ему КА M’(Q’,V’,G’,q0’,F’), задающий тот же язык

L(M) = L(M’), не содержащий недостижимых состояний

Дополнительные условия: нет

162

Устранение недостижимых состояний КА

1. V’ = V, q0’ = q0 , Q’ = {q0}

2. Q’ = Q’ { qj | qi Q’: G(qi, vk)=qj, k=1,2,..,|V| }

Итерационно включаются все состояния, в которые можно попасть из начального

3. G ’ = {G (qi,vk) | qi Q’ }

4. F ’ = F Q ’

163

Устранение недостижимых состояний КА

Пример

М ( {A,B,C,D,E,F,G}, {0,1}, G, A ,{D, E})

G	A	B	C	D	E	F	G
0	B			C	B	D	F
1	C	D	E	E	D	G	F

0	B	1	D	0	F
		0	1	0,1	1
A
				1
1	C	0	E		G
		1
					164

Устранение недостижимых состояний КА

1. V’ = {0, 1}, q0 = A, Q = {A}

2.1. Q = {A, B, C}

G

A

B

C

D

E

F

G

0 B

D

E

C B D

F

0

B

1

D

0

F

1

C

E

D

G

F

0

1

0,1

1

A

1

1

C

0

E

G

1

165

Устранение недостижимых состояний КА

2.2. Q = {A, B, C, D, E}

G

A

B

C

D

E

F

G

0 B

D

E

C B D

F

0

B

1

D

0

F

1

C

E

D

G

F

0

1

0,1

1

A

1

1

C

0

E

G

1

166

Устранение недостижимых состояний КА

2.3. Q = {A, B, C, D, E}

G

A

B

C

D

E

F

G

0 B

D

E

C B D

F

0

B

1

D

0

F

1

C

E

D

G

F

0

1

0,1

1

A

1

1

C

0

E

G

1

167

Устранение недостижимых состояний КА

	3.								1
							0 B			D
	G	A	B	C	D	E			0
	0	B			C	B	A			1
	1	C	D	E	E	D	1	C	0	1
									1	E
	4. F’ = F Q ’ = {D,E} {A,B,C,D,E} = {D,E}

168

Объединение эквивалентных состояний КА

Состояния q, q’ Q называются n- эквивалентными, nt0, если, находясь в

одном из этих состояний и получив на вход произвольную цепочку Z V *, |Z|dn, КА

может перейти в одно и то же множество конечных состояний

Для цепочки длиной не более n эти состояния могут вести себя совершенно одинаково

169

Объединение эквивалентных состояний КА

0-эквивалентными состояниями КА будут F

и Q\F

Множества эквивалентных состояний называются классами эквивалентности

совокупность классов эквивалентности – множеством классов эквивалентности R(n)

R(0)={F, Q\F}

170