Jezični procesori 1

Korice......Page 1
Sadržaj......Page 5
UVOD......Page 7
1.1 ZNAKOVLJE I OZNAKE......Page 14
1.2 PRIMJER FORMALNOG JEZIKA, PRIPADAJUĆEG AUTOMATA l GRAMATIKE......Page 18
2.1.1 Deterministički konačni automat (DKA)......Page 21
2.1.2 Minimizacija konačnog automata......Page 28
2.1.3 Nedeterministički konačni automat (NKA)......Page 35
2.1.4 Nedeterministički konačni automat s ε prijelazima (ε-NKA)......Page 40
2.1.5 Konačni automati s izlazom......Page 45
2.2.1 Definicija regularnih izraza......Page 50
2.2.2 Konstrukcija ε-NKA na temelju zadanih regularnih izraza......Page 52
2.2.3 Generator konačnog automata......Page 56
2.3.1 Svojstva zatvorenosti regularnih jezika......Page 57
2.3.2 Regularne definicije......Page 59
2.3.3 Svojstvo napuhavanja......Page 60
2.4.1 Formalna gramatika......Page 62
2.4.2 Regularna gramatika......Page 68
3.1.1 Nejednoznačnost gramatike, jezika i niza......Page 75
3.1.2 Pojednostavljenje gramatike......Page 82
3.1.3 Parsiranje niza......Page 95
3.2.1 Model potisnog automata......Page 109
3.2.2 Definicija potisnog automata......Page 112
3.2.3 Potisni automat i kontekstno neovisna gramatika......Page 116
3.3 SVOJSTVA KONTEKSTNO NEOVISNIH JEZIKA......Page 124
3.3.1 Svojstva zatvorenosti kontekstno neovisnih jezika......Page 125
3.3.2 Svojstvo napuhavanja......Page 130
4.1.1 Osnovni model Turingovog stroja......Page 132
4.1.2 Metode izrade Turingovog stroja......Page 140
4.1.3 Prošireni modeli Turingovog stroja......Page 145
4.1.4 Pojednostavljeni modeli Turingovog stroja......Page 152
4.1.5 Generiranje jezika Turingovim strojem......Page 156
4.2 GRAMATIKA NEOGRANIČENIH PRODUKCUA......Page 158
4.2.1 Konstrukcija TS za jezik zadan gramatikom neograničenih produkcija......Page 159
4.2.2 Konstrukcija gramatike za jezik zadan TS......Page 160
4.3.1 Svojstva zatvorenosti rekurzivnih i rekurzivno prebrojivih jezika......Page 162
4.3.2 1zračunljivost......Page 164
4.3.3 Odlučivost......Page 169
5.1 KONTEKSTNO OVISNA GRAMATIKA......Page 171
5.2 LINEARNO OGRANIČEN AUTOMAT (LOA)......Page 173
5.2.2 Konstrukcija kontekstno ovisne gramatike za jezik zadan LOA......Page 174
5.3.1 Unija, nadovezivanje i Kleeneov operator......Page 176
5.3.2 Presjek i komplement......Page 177
5.3.3 Odlučivost kontekstno ovisnih jezika......Page 179
5.3.4 Primjer rekurzivnog jezika koji nije kontekstno ovisni jezik......Page 180
6.1 STRUKTURNA SLOŽENOST JEZIKA......Page 183
6.1.1 Chomskyjeva hijerarhija jezika......Page 184
6.1.2 Hijerarhija gramatika i automata......Page 185
6.2 SLOŽENOST PRIHVAĆANJA JEZIKA......Page 186
6.2.1 Definicija prostorne i vremenske složenosti prihvaćanja jezika......Page 187
6.2.2 Svojstva prostorne i vremenske složenosti prihvaćanja jezika......Page 189
6.2.3 Klase jezika s obzirom na složenost prihvaćanja jezika......Page 193
6.2.4 Klase jezika polinomne složenosti......Page 200
Kazalo pojmova s hratsko-engleskim rječnikom......Page 206