Limbaje Formale si Translatoare

Imagine preview
(9/10 din 3 voturi)

Acest curs prezinta Limbaje Formale si Translatoare.
Mai jos poate fi vizualizat cuprinsul si un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier pdf de 229 de pagini .

Profesor: Gavrila Ionut

Iti recomandam sa te uiti bine pe extras, cuprins si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Calculatoare

Cuprins

Cuprins
1 Ierarhia lui Chomsky. Generari de limbaje 3
1.1 Introducere 3
1.2 Generari de limbaje 5
1.3 Exercitii propuse spre rezolvare 24
2 Automate nite 38
2.1 Introducere 38
2.2 Sumatorul binar 41
2.3 Relatiile A;s0 si L 44
2.4 Constructia automatului minimal 54
2.5 Legatura dintre automate nite deterministe si cele nite nedeterministe 61
2.6 Legatura dintre limbaje regulate si automate nite 65
2.7 Lema de pompare Bar-Hillel 71
2.8 Sisteme tranzitionale 74
2.8.1 Un algoritm e cient pentru conversia dintre un sistem tranzitional
si un automat nit nedeterminist 76
2.9 Expresii regulate 80
2.10 Exercitii propuse spre rezolvare 95
3 Limbaje independente de context 104
3.1 Automate pushdown nedeterministe 104
3.1.1 Un algoritm e cient pentru conversia dintre un automat push-
down nedeterminist si o gramatica de tip 2 112
3.2 Lema de pompare pentru limbaje de tip 2 116
3.3 Forma normala Chomsky 124
3.4 Forma normala Greibach 127
3.5 Forma normala operator 132
3.5.1 Un algoritm e cient pentru conversia dintre o gramatica ^n
forma normala Chomsky si o gramatica^n forma normala operator134
3.6 Limbaje independente de context deterministe 136
3.7 Probleme decidabile ^n clasa L2 138
3.7.1 Un algoritm e cient de analiza sintactica pentru gramatici ^n
forma normala Chomsky 145
1
2
3.8 Problema echivalentei a doua gramatici independente de context 152
3.9 Exercitii propuse spre rezolvare 156
4 Masini Turing si automate liniar marginite 163
4.1 Masini Turing 163
4.2 Automate liniar marginite 178
4.3 Legatura dintre gramaticile dependente de context si gramaticile mono-
tone 180
4.4 Exercitii propuse spre rezolvare 186

Extras din document

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

Fisiere in arhiva (1):

  • Limbaje Formale si Translatoare.pdf