09_Gramatyki_generatywne.pdf

(134 KB) Pobierz
GRAMATYKI GENERATYWNE
Def. nazywamy ukþad
(((( ))))
====
,
,
,
taki, Ňe
- jest skoıczonym alfabetem (podstawowym),
,
- jest skoıczonym alfabetem (pomocniczym),
,
====
-
(symbol poczĢtkowy),
- P jest skoıczonym zbiorem reguþ produkcji postaci
(((( ))))
a , gdzie
,
,
.
Def. Niech
= == = bħdzie gramatykĢ generatywnĢ.
( (( ( ) )) )
,
,
,
OkreĻlamy relacjħ
(
w ) nastħpujĢco:
jeŇeli istniejĢ
,
,
,
, takie Ňe
( (( ( ) )) )
,
a
==== ,
==== .
OkreĻlamy relacjħ
( w )
nastħpujĢco:
jeŇeli istniejĢ
0 K
,
,
, takie Ňe
==== ,
0
0
==== oraz
dla kaŇdego
.
1
−−−− 1
Def.
==== :
(((( ))))
,
,
,
(((()))) {{{{}}}}
==== :
.
Def. Gramatykħ generatywnĢ
==== nazywamy
s , jeŇeli wszystkie reguþy produkcji tej
gramatyki maja postaę
(((( ))))
,
,
,
a ,
(((( ))))
gdzie
,
.
Jħzyki generowane przez gramatyki bezkontekstowe
nazywamy s .
Def. Gramatyki
1 i
2 sĢ , jeŇeli generujĢ te
same jħzyki, tzn.
==== .
( (( () )) )( (( () )) )
1
2
Fakt. KaŇdĢ gramatykħ bezkontekstowĢ moŇna przeksztaþcię
do rwnowaŇnej gramatyki o reguþach produkcji postaci:
K
a 2
,
,
,
0
.
1
a ,
,
.
Niech
= == = - gramatyka bezkontekstowa.
( (( ( ) )) )
,
,
,
Tworzymy
= == =
(((( ))))
,
,
,
nastħpujĢco:
{{{{}}}}
: ,
powstaje z wedþug zasady:
====
a) w kaŇdej regule
(((( ))))
wszystkie
a
zastħpujemy przez
,
b) dodajemy reguþy postaci
a

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin