Capitolul 1
Ierarhia lui Chomsky.
Generari de limbaje
1.1 Introducere
Termenul de gramatica a fost atribuit sistemelor generative din respect pentru lingvis-
tul si losoful Noam Chomsky1. Domnia sa este primul care a folosit aceste sisteme
generative pentru de nirea unei gramatici sintactice" pentru limba engleza. Printre
alte rezultate referitoare la gramaticile formale, ^n anul 1956, acesta le clasi ca pe
tipuri, clasi care care ^i poarta numele.
De nitia 1.1.1 Numim alfabet o multime nita si nevida (elementele sale le numim
simboluri). Vom numi cuv^ant peste V o aplicatie p : f1; 2; :::; ng ! V; numarul
n = jpj numindu-se lungimea cuv^antului p:
Notatia 1.1.1 Prin V
n = fp=p : f1; 2; :::; ng ! V g ^ntelegem multimea cuvintelor
de lungime n: Notam cu V - = S n0
V
n si cu V
+ = S n1
V
n
:
De nitia 1.1.2 Se numeste gramatica (sau sistem generativ) un 4-uplu G =
(VN; VT ; x0; P), unde:
- VN este o multime nita si nevida, numita multimea neterminalilor (vari-
abilelor);
- VT este o multime nita si nevida, numita multimea terminalilor, astfel
^nc^at:
{ VN VT = ;;
{ V = VN [ VT se numeste alfabetul gramaticii G;
1Profesor la Departamentul de lingvistica si loso e, Massachusetts Institute of Technology, Cam-
bridge, U.S.A.
3
Introducere 4
- x0 2 VN este simbolul de start al gramaticii G;
- P - V - VN V - V - este multimea regulilor de generare (productiilor).
Notatia 1.1.2 Pentru o gramatica G; o regula din P se noteaza cu (u; v) sau u ! v:
De nitia 1.1.3 Fie G = (VN; VT ; x0; P) o gramatica arbitrara. Se numeste
derivare directa (derivare ^ntr-un pas) relatia binara =)
G
- V
- V
- de nita astfel:
( ; ) 2=)
G
daca 9 u ! v 2 P astfel ^nc^at = 1u 2; = 1v 2:
Notatia 1.1.3 Pentru ( ; ) 2=)
G
se utilizeaza de obicei notatia =)
G
:
De nitia 1.1.4 ^Inchiderea re
exiva si tranzitiva a relatiei de derivare directa se
numeste derivare. Mai precis, vom spune ca se deriveaza din ^n G; notatie
- =)
G
, daca
- = sau
- 9 n 1 si 9 u1; u2; :::; un astfel ^nc^at = u1; = un si ui =)
G
ui+1; 8 i =
1; n
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
