spoPresentation2

Преобразование КА к детерминированному виду

Для любого КА можно построить эквивалентный ему детерминированный КА

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

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

задающую тот же язык L(M) = L(M’)

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

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

151

Преобразование КА к детерминированному виду

2. qi’ Q’ : G(qi’, vj’) = {qij’ | {G(qk,vj)}, qi’ qk }, Q’=Q’ qij’ , j=1,2,..,|V|. Итерационно

формируем новые состояния и переходы

3. F’ = {qi’ | qi’ Q’ : qi’ qk , qk F }

Пример

M ( { J,C,K,A,B,D,E,H }, {/,*,a,p,m}, G, H, {J})

1. V’ = {/,*,a,p,m}; q0’= H; Q’={H};

152

Преобразование КА к детерминированному виду

2. qi’ Q’ : G(qi’, vj’) = {qij’ | {G(qk,vj)}, qi’ qk }, Q’=Q’ qij’ , j=1,2,..,|V|

2.1.

G J	C	K A B D E H
/	C	K J	K E
*	C, A	K	C
a	C	K
p	D	B
m			J C

G ’ H E

/ E

*

a

p

m

153

Преобразование КА к детерминированному виду

2. qi’ Q’ : G(qi’, vj’) = {qij’ | {G(qk,vj)}, qi’ qk }, Q’=Q’ qij’ , j=1,2,..,|V|

2.2.

G J	C	K A B D E H
/	C	K J	K E
*	C, A	K	C
a	C	K
p	D	B
m			J C

G ’	H E K C
/	E K
*	C
a
p
m

154

Преобразование КА к детерминированному виду

2. qi’ Q’ : G(qi’, vj’) = {qij’ | {G(qk,vj)}, qi’ qk }, Q’=Q’ qij’ , j=1,2,..,|V|

2.3.

G J	C K A B D E H
/	C K J	K E
*	C,A K	C
a	C K

pD B

m

J C

G ’	H	E	K	C B CA D
/	E	K	K	C
*		C	K	CA
a			K	C
p			B	D
m

155

Преобразование КА к детерминированному виду

2. qi’ Q’ : G(qi’, vj’) = {qij’ | {G(qk,vj)}, qi’ qk }, Q’=Q’ qij’ , j=1,2,..,|V|

2.4.

G J	C K A B D E H
/	C K J	K E
*	C,A K	C
a	C K

pD B

m

J C

G’ H E K C B CA D J CJ
/	E K K	C	CJ
*	C K CA		CA
a	K	C	C
p	B	D	D
m		J	C

156

Преобразование КА к детерминированному виду

2. qi’ Q’ : G(qi’, vj’) = {qij’ | {G(qk,vj)}, qi’ qk }, Q’=Q’ qij’ , j=1,2,..,|V|

2.5.

G J	C K A B D E H
/	C K J	K E
*	C,A K	C
a	C K

pD B

m

J C

G’ H E K C B CA D J				CJ
/	E K K	C	CJ	C
*	C K CA		CA	CA
a	K	C	C	C
p	B	D	D	D
m		J	C

157

Преобразование КА к детерминированному виду

3. F’ = {qi’ | qi’ Q’ : qi’ qk , qk F }

3. F’ = { J, CJ }

G J	C K A B D E H
/	C K J	K E
*	C,A K	C
a	C K

pD B

m

J C

G’ H E K C B CA D J				CJ
/	E K K	C	CJ	C
*	C K CA		CA	CA
a	K	C	C	C
p	B	D	D	D
m		J	C

158

Преобразование КА к детерминированному виду

G ‘ H E K C B A D J Y
/	E K K	C	Y	C
*	C K	A	A	A
a	K	C	C	C
p	B	D	D	D
m			J	C

F ’ = { J, Y}

159

Преобразование КА к детерминированному виду

					p		D	p
					*	m	p
				C			A	Y
			*	/ ,				*
H		E		/ , * , a				/ , a
	/			K			B	m J
		/			p

160