spoPresentation2

Конечные автоматы

КА M (Q, V, G, q0, F) называется детерминированным КА, если a V, q Q:

G(q,a)={r}, r Q либо G(q,a)=

т.е. в каждом из его состояний для любого входного символа функция перехода содержит не более одного состояния

Иначе КА недетерминированный

131

Связь КА и синтаксических диаграмм

<

>

=	=	< , >
!	A	C
<
>
=	=	B

!

132

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

Дано: регулярная леволинейная грамматика

G(T,N,P,S), задающая язык L (G)

Получить: эквивалентный ей КА

M(Q,V,G,q0,F), задающий тот же язык L(M) =

L(G)

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

1. Исходная грамматика G(T,N,P,S) преобразуется в эквивалентную ей автоматную грамматику G’(T’,N’,P’,S’)

133

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

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

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

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

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

134

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

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

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

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

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

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

135

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

Пример

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

Р = { J o A/ | Bm

C o C/ | C* | Ca | Dm | E* K o K/ | K* | Ka | E/

A o C* B o Kp D o Cp E o / }

136

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

Пример

2.1. Q = { J,C,K,A,B,D,E,H }; V={ /,*,a,p,m }; q0 = H; F = {J}

	2.2. E o /		G ( H, / ) = {E}
	2.3.1. J o A/		G ( A, / ) = {J}
	2.3.2. J o Bm		G ( B, m ) = {J}
	2.3.3. C o C/		G ( C, / ) = {C}
	2.3.4. C o C* ; A o C* G ( C, * ) = {C, A}
	2.3.5. C o Ca		G ( C, a ) = {C}
	2.3.6. C o Dm		G ( D, m ) = {C}

137

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

2.3.7. C o E*		G ( E, * ) = {C}
2.3.8. K o K/		G ( K, / ) = {K}
2.3.9. K o K*		G ( K, * ) = {K}
2.3.10. K o Ka		G ( K, a ) = {K}
2.3.11. K o E/		G ( E, / ) = {K}
2.3.12. B o Kp		G ( K, p ) = {B}
2.3.13. D o Cp		G ( C,p ) = {D}

138

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

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

H /

КА недетерминирован

КА не полностью определен

D

pm

*	C	*	A	/
		/ , * , a		J
E
		/ , * , a
/				m
	K		B
		p
				139

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

Дано: регулярная праволинейная грамматика

G(T,N,P,S), задающая язык L (G)

Получить: эквивалентный ей КА

M(Q,V,G,q0,F), задающий тот же язык L(M) =

L(G)

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

1. Исходная грамматика G(T,N,P,S) преобразуется в эквивалентную ей автоматную грамматику G’(T’,N’,P’,S’)

140