spoPresentation2

Построение КА по праволинейной грамматике

2. На основе полученной грамматики G’(T’,N’,P’,S’) строится искомый КА

M(Q,V,G,q0,F)

2.1. Q = N’ {H}; V=T’; q0=S’; F={H}.

Множество состояний соответствует нетерминальному словарю, к которым добавляется еще одно состояние H. Входной алфавит – множеству терминальных символов. Начальное состояние - аксиома S’. Множество конечных состояний – H

141

Построение КА по праволинейной грамматике

2.2. G (A, t) = { H }, p P’ : Aot, A N’, t T’ }. В

функцию переходов для состояний A добавляется состояние H

2.3. G (A, t) = { B | p P’ : Ao tВ, A,В N’, t T’}.

В функцию переходов для состояния A

добавляются состояния B

142

Построение леволинейной грамматики по КА

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

Получить: эквивалентную ему регулярную леволинейную грамматику G(T,N,P,S), задающую тот же язык L(M) = L(G)

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

1. T = V; N = Q \ {q0} . Множество

терминальных символов соответствует входному алфавиту, нетерминальных - множеству состояний за исключением начального

143

Построение леволинейной грамматики по КА

2.1. S = {F0 }, если F = {F0}

2.2. S = {F0 }, N = N {F0}, P = P {SoF1 | F2 |…|

Fn}, если F = {F1, F2,…, Fn }, n >1

Если у автомата одно конечное состояние, оно становится аксиомой грамматики

Если у автомата несколько конечных состояний, то добавляется новый

нетерминал F0, который и станет аксиомой, и пополняется множество правил

144

Построение леволинейной грамматики по КА

3. P = P { Bkot | G(q0,t) = { B1, B2,…, Bn }, n>0, Bk Q, k=1,2,..,n, t V } Пополняется

множество правил

4. P = P { BkoAt | G(A,t) = { B1, B2,…, Bn }, A z q0 , A Q, n>0, Bk Q, k=1,2,..,n, t V }

145

Построение праволинейной грамматики по КА

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

Получить: эквивалентную ему регулярную праволинейную грамматику G(T,N,P,S), задающую тот же язык L(M) = L(G)

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

1. T = V; N = Q; S = q0 . Множество

терминальных символов соответствует входному алфавиту, нетерминальных - множеству состояний, аксиоме – начальное состояние

146

Построение праволинейной грамматики по КА

2. P = P { AotBk | G(A,t) = {B1, B2,…, Bn}, n>0, A, Bk Q, Bk F, k=1,2,..,n, t V }

3. P = P { Aot | G(A,t) = {B1, B2,…, Bn}, n>0, A, Bk Q, Bk F, k=1,2,..,n, t V }

4. P = P { AotBk | G(A,t)={B1, B2,…, Bn}, n>0, A, Bk Q, Bk F, k=1,2,..,n, t V, G(Bk,t’) = {C1, C2,…,

Cm} Cj Q, j=1,2,..,m, t’ V } Пополняется

множество правил, если есть переходы из конечных состояний

147

Построение праволинейной грамматики по КА

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

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

A /

J

m

B

148

Построение праволинейной грамматики по КА

1. T={/,*,a,p,m}; N={J,C,K,A,B,D,E,H}; S=H

2.1. G(C,/) = {C} P = P {Co/C}

2.2. G(C,*) = {C,A} P = P {Co*C | *A}

2.3. P = P {CoaC}

2.4. P = P {CopD}

2.5. P = P {Ko/K | *K | aK | pB}

2.6. P = P {DomС}

2.7. P = P {Eo/K | *C}

2.8. P = P {Ho/E}

149

Построение праволинейной грамматики по КА

3.1. G(A,/) = { J } P = P {Ao/}

3.2. G(B,m) = { J } P = P {Bom}

4. Если бы из состояния J были переходы, то добавились бы Ao/J; BomJ

P: { Ao/	DomС
Bom	Eo/K | *C
Co/C | *C | *A | aC | pD	Ho/E
Ko/K | *K | aK | pB
}

150