Limbaje Formale și Translatoare

Curs
9.3/10 (3 voturi)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 229 în total
Cuvinte : 71712
Mărime: 1.12MB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Gavrila Ionut

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

Preview document

Limbaje Formale și Translatoare - Pagina 1
Limbaje Formale și Translatoare - Pagina 2
Limbaje Formale și Translatoare - Pagina 3
Limbaje Formale și Translatoare - Pagina 4
Limbaje Formale și Translatoare - Pagina 5
Limbaje Formale și Translatoare - Pagina 6
Limbaje Formale și Translatoare - Pagina 7
Limbaje Formale și Translatoare - Pagina 8
Limbaje Formale și Translatoare - Pagina 9
Limbaje Formale și Translatoare - Pagina 10
Limbaje Formale și Translatoare - Pagina 11
Limbaje Formale și Translatoare - Pagina 12
Limbaje Formale și Translatoare - Pagina 13
Limbaje Formale și Translatoare - Pagina 14
Limbaje Formale și Translatoare - Pagina 15
Limbaje Formale și Translatoare - Pagina 16
Limbaje Formale și Translatoare - Pagina 17
Limbaje Formale și Translatoare - Pagina 18
Limbaje Formale și Translatoare - Pagina 19
Limbaje Formale și Translatoare - Pagina 20
Limbaje Formale și Translatoare - Pagina 21
Limbaje Formale și Translatoare - Pagina 22
Limbaje Formale și Translatoare - Pagina 23
Limbaje Formale și Translatoare - Pagina 24
Limbaje Formale și Translatoare - Pagina 25
Limbaje Formale și Translatoare - Pagina 26
Limbaje Formale și Translatoare - Pagina 27
Limbaje Formale și Translatoare - Pagina 28
Limbaje Formale și Translatoare - Pagina 29
Limbaje Formale și Translatoare - Pagina 30
Limbaje Formale și Translatoare - Pagina 31
Limbaje Formale și Translatoare - Pagina 32
Limbaje Formale și Translatoare - Pagina 33
Limbaje Formale și Translatoare - Pagina 34
Limbaje Formale și Translatoare - Pagina 35
Limbaje Formale și Translatoare - Pagina 36
Limbaje Formale și Translatoare - Pagina 37
Limbaje Formale și Translatoare - Pagina 38
Limbaje Formale și Translatoare - Pagina 39
Limbaje Formale și Translatoare - Pagina 40
Limbaje Formale și Translatoare - Pagina 41
Limbaje Formale și Translatoare - Pagina 42
Limbaje Formale și Translatoare - Pagina 43
Limbaje Formale și Translatoare - Pagina 44
Limbaje Formale și Translatoare - Pagina 45
Limbaje Formale și Translatoare - Pagina 46
Limbaje Formale și Translatoare - Pagina 47
Limbaje Formale și Translatoare - Pagina 48
Limbaje Formale și Translatoare - Pagina 49
Limbaje Formale și Translatoare - Pagina 50
Limbaje Formale și Translatoare - Pagina 51
Limbaje Formale și Translatoare - Pagina 52
Limbaje Formale și Translatoare - Pagina 53
Limbaje Formale și Translatoare - Pagina 54
Limbaje Formale și Translatoare - Pagina 55
Limbaje Formale și Translatoare - Pagina 56
Limbaje Formale și Translatoare - Pagina 57
Limbaje Formale și Translatoare - Pagina 58
Limbaje Formale și Translatoare - Pagina 59
Limbaje Formale și Translatoare - Pagina 60
Limbaje Formale și Translatoare - Pagina 61
Limbaje Formale și Translatoare - Pagina 62
Limbaje Formale și Translatoare - Pagina 63
Limbaje Formale și Translatoare - Pagina 64
Limbaje Formale și Translatoare - Pagina 65
Limbaje Formale și Translatoare - Pagina 66
Limbaje Formale și Translatoare - Pagina 67
Limbaje Formale și Translatoare - Pagina 68
Limbaje Formale și Translatoare - Pagina 69
Limbaje Formale și Translatoare - Pagina 70
Limbaje Formale și Translatoare - Pagina 71
Limbaje Formale și Translatoare - Pagina 72
Limbaje Formale și Translatoare - Pagina 73
Limbaje Formale și Translatoare - Pagina 74
Limbaje Formale și Translatoare - Pagina 75
Limbaje Formale și Translatoare - Pagina 76
Limbaje Formale și Translatoare - Pagina 77
Limbaje Formale și Translatoare - Pagina 78
Limbaje Formale și Translatoare - Pagina 79
Limbaje Formale și Translatoare - Pagina 80
Limbaje Formale și Translatoare - Pagina 81
Limbaje Formale și Translatoare - Pagina 82
Limbaje Formale și Translatoare - Pagina 83
Limbaje Formale și Translatoare - Pagina 84
Limbaje Formale și Translatoare - Pagina 85
Limbaje Formale și Translatoare - Pagina 86
Limbaje Formale și Translatoare - Pagina 87
Limbaje Formale și Translatoare - Pagina 88
Limbaje Formale și Translatoare - Pagina 89
Limbaje Formale și Translatoare - Pagina 90
Limbaje Formale și Translatoare - Pagina 91
Limbaje Formale și Translatoare - Pagina 92
Limbaje Formale și Translatoare - Pagina 93
Limbaje Formale și Translatoare - Pagina 94
Limbaje Formale și Translatoare - Pagina 95
Limbaje Formale și Translatoare - Pagina 96
Limbaje Formale și Translatoare - Pagina 97
Limbaje Formale și Translatoare - Pagina 98
Limbaje Formale și Translatoare - Pagina 99
Limbaje Formale și Translatoare - Pagina 100
Limbaje Formale și Translatoare - Pagina 101
Limbaje Formale și Translatoare - Pagina 102
Limbaje Formale și Translatoare - Pagina 103
Limbaje Formale și Translatoare - Pagina 104
Limbaje Formale și Translatoare - Pagina 105
Limbaje Formale și Translatoare - Pagina 106
Limbaje Formale și Translatoare - Pagina 107
Limbaje Formale și Translatoare - Pagina 108
Limbaje Formale și Translatoare - Pagina 109
Limbaje Formale și Translatoare - Pagina 110
Limbaje Formale și Translatoare - Pagina 111
Limbaje Formale și Translatoare - Pagina 112
Limbaje Formale și Translatoare - Pagina 113
Limbaje Formale și Translatoare - Pagina 114
Limbaje Formale și Translatoare - Pagina 115
Limbaje Formale și Translatoare - Pagina 116
Limbaje Formale și Translatoare - Pagina 117
Limbaje Formale și Translatoare - Pagina 118
Limbaje Formale și Translatoare - Pagina 119
Limbaje Formale și Translatoare - Pagina 120
Limbaje Formale și Translatoare - Pagina 121
Limbaje Formale și Translatoare - Pagina 122
Limbaje Formale și Translatoare - Pagina 123
Limbaje Formale și Translatoare - Pagina 124
Limbaje Formale și Translatoare - Pagina 125
Limbaje Formale și Translatoare - Pagina 126
Limbaje Formale și Translatoare - Pagina 127
Limbaje Formale și Translatoare - Pagina 128
Limbaje Formale și Translatoare - Pagina 129
Limbaje Formale și Translatoare - Pagina 130
Limbaje Formale și Translatoare - Pagina 131
Limbaje Formale și Translatoare - Pagina 132
Limbaje Formale și Translatoare - Pagina 133
Limbaje Formale și Translatoare - Pagina 134
Limbaje Formale și Translatoare - Pagina 135
Limbaje Formale și Translatoare - Pagina 136
Limbaje Formale și Translatoare - Pagina 137
Limbaje Formale și Translatoare - Pagina 138
Limbaje Formale și Translatoare - Pagina 139
Limbaje Formale și Translatoare - Pagina 140
Limbaje Formale și Translatoare - Pagina 141
Limbaje Formale și Translatoare - Pagina 142
Limbaje Formale și Translatoare - Pagina 143
Limbaje Formale și Translatoare - Pagina 144
Limbaje Formale și Translatoare - Pagina 145
Limbaje Formale și Translatoare - Pagina 146
Limbaje Formale și Translatoare - Pagina 147
Limbaje Formale și Translatoare - Pagina 148
Limbaje Formale și Translatoare - Pagina 149
Limbaje Formale și Translatoare - Pagina 150
Limbaje Formale și Translatoare - Pagina 151
Limbaje Formale și Translatoare - Pagina 152
Limbaje Formale și Translatoare - Pagina 153
Limbaje Formale și Translatoare - Pagina 154
Limbaje Formale și Translatoare - Pagina 155
Limbaje Formale și Translatoare - Pagina 156
Limbaje Formale și Translatoare - Pagina 157
Limbaje Formale și Translatoare - Pagina 158
Limbaje Formale și Translatoare - Pagina 159
Limbaje Formale și Translatoare - Pagina 160
Limbaje Formale și Translatoare - Pagina 161
Limbaje Formale și Translatoare - Pagina 162
Limbaje Formale și Translatoare - Pagina 163
Limbaje Formale și Translatoare - Pagina 164
Limbaje Formale și Translatoare - Pagina 165
Limbaje Formale și Translatoare - Pagina 166
Limbaje Formale și Translatoare - Pagina 167
Limbaje Formale și Translatoare - Pagina 168
Limbaje Formale și Translatoare - Pagina 169
Limbaje Formale și Translatoare - Pagina 170
Limbaje Formale și Translatoare - Pagina 171
Limbaje Formale și Translatoare - Pagina 172
Limbaje Formale și Translatoare - Pagina 173
Limbaje Formale și Translatoare - Pagina 174
Limbaje Formale și Translatoare - Pagina 175
Limbaje Formale și Translatoare - Pagina 176
Limbaje Formale și Translatoare - Pagina 177
Limbaje Formale și Translatoare - Pagina 178
Limbaje Formale și Translatoare - Pagina 179
Limbaje Formale și Translatoare - Pagina 180
Limbaje Formale și Translatoare - Pagina 181
Limbaje Formale și Translatoare - Pagina 182
Limbaje Formale și Translatoare - Pagina 183
Limbaje Formale și Translatoare - Pagina 184
Limbaje Formale și Translatoare - Pagina 185
Limbaje Formale și Translatoare - Pagina 186
Limbaje Formale și Translatoare - Pagina 187
Limbaje Formale și Translatoare - Pagina 188
Limbaje Formale și Translatoare - Pagina 189
Limbaje Formale și Translatoare - Pagina 190
Limbaje Formale și Translatoare - Pagina 191
Limbaje Formale și Translatoare - Pagina 192
Limbaje Formale și Translatoare - Pagina 193
Limbaje Formale și Translatoare - Pagina 194
Limbaje Formale și Translatoare - Pagina 195
Limbaje Formale și Translatoare - Pagina 196
Limbaje Formale și Translatoare - Pagina 197
Limbaje Formale și Translatoare - Pagina 198
Limbaje Formale și Translatoare - Pagina 199
Limbaje Formale și Translatoare - Pagina 200
Limbaje Formale și Translatoare - Pagina 201
Limbaje Formale și Translatoare - Pagina 202
Limbaje Formale și Translatoare - Pagina 203
Limbaje Formale și Translatoare - Pagina 204
Limbaje Formale și Translatoare - Pagina 205
Limbaje Formale și Translatoare - Pagina 206
Limbaje Formale și Translatoare - Pagina 207
Limbaje Formale și Translatoare - Pagina 208
Limbaje Formale și Translatoare - Pagina 209
Limbaje Formale și Translatoare - Pagina 210
Limbaje Formale și Translatoare - Pagina 211
Limbaje Formale și Translatoare - Pagina 212
Limbaje Formale și Translatoare - Pagina 213
Limbaje Formale și Translatoare - Pagina 214
Limbaje Formale și Translatoare - Pagina 215
Limbaje Formale și Translatoare - Pagina 216
Limbaje Formale și Translatoare - Pagina 217
Limbaje Formale și Translatoare - Pagina 218
Limbaje Formale și Translatoare - Pagina 219
Limbaje Formale și Translatoare - Pagina 220
Limbaje Formale și Translatoare - Pagina 221
Limbaje Formale și Translatoare - Pagina 222
Limbaje Formale și Translatoare - Pagina 223
Limbaje Formale și Translatoare - Pagina 224
Limbaje Formale și Translatoare - Pagina 225
Limbaje Formale și Translatoare - Pagina 226
Limbaje Formale și Translatoare - Pagina 227
Limbaje Formale și Translatoare - Pagina 228
Limbaje Formale și Translatoare - Pagina 229

Conținut arhivă zip

  • Limbaje Formale si Translatoare.pdf

Alții au mai descărcat și

Rețele de Calculatoare

Lucrarea Modele si solutii pentru administrarea reteleor de calculatoare contine o prezentare succinta a protocolului de administrare SNMP...

Criptografie si Securitatea Informatiei

1.1 Noţiuni de teoria numerelor 1.1.1 Numere prime Fiind date două numere naturale m şi n, spunem că m divide pe n, sau că n este multiplu al...

Multiprocesoare

INTRODUCERE “Necesarul de simulări al Departamentului pentru Energie (DOE) al Statelor Unite depăşeşte cu mult capacitatea celor mai puternice...

Procesorul - Caile de Date si Unitatea de Control

Suntem gata sa implementam procesorul MIPS: Cap 2: performanta unei masini e determinata de 3 factori cheie: nr de instructiuni, durata ciclului...

Limbaje Formale și Translatoare

1. Introducere Curs1 LFT Limbajele de nivel înalt au o serie de avantaje în raport cu limbajele de asamblare. Pentru a putea însă folosi limbaje...

Criptografie

Caracteristicile unui sistem de criptare 1. Confident¸ialitate (privacy): proprietatea de a p˘astra secretul informat¸iei, pentru ca aceasta s˘a...

Rețele Neuronale și Logica Fuzzy în Automatizări

Prefaţă În proiectarea sistemelor de reglare automată, un algoritm competitiv ar trebui să valorifice orice fel de informaţie legată de procesul...

Microcontrolere PIC

Capitolul 1: microcontroler PIC16F887 - Dispozitiv de ansamblu asupra PIC16F887 este una dintre cele mai noi produse de Microchip. Conţine toate...

Ai nevoie de altceva?