Formális nyelvek és automaták

Formális Nyelvek és Automaták......Page 1
Tartalom......Page 3
1. fejezet - Bevezetés......Page 7
2.1. Ábécé, szó, formális nyelv, szabad monoid, szabad félcsoport......Page 11
2.2. Nyelvmuveletek......Page 13
3. fejezet - Formális rendszer és néhány fobb típusa......Page 16
3.1. Markov-féle normál algoritmus......Page 20
3.2. Generatív nyelvtan, Chomsky-féle nyelvosztályok......Page 26
3.2.1. Chomsky-féle nyelvosztályok......Page 29
3.2.2. A Chomsky hierarchia......Page 36
3.3. L-rendszerek......Page 40
3.4.1. Normálformák (Normálalakok)......Page 42
3.4.3. A szóprobléma és a szintaktikai elemzés......Page 43
3.4.6. Speciális alosztályok......Page 44
4.1.1. Mealy automata......Page 45
4.1.3. Kimenojel nélküli automata......Page 46
4.1.6. Nemdeterminisztikus és determinisztikus automata......Page 47
4.1.8. Rabin-Scott automata......Page 48
4.2.1.2. Véges Moore-automata Cayley táblája......Page 50
4.2.1.3. Véges kimenojel nélküli automata Cayley táblája......Page 51
4.2.2.2. Véges Moore-automata megadása gráffal......Page 52
4.2.2.3. Véges kimenojel nélküli automata megadása gráffal......Page 53
4.3.1. Mealy automata, mint algebrai struktúra......Page 54
4.3.2. Moore automata, mint algebrai struktúra......Page 56
4.4. Az automaták által indukált leképezések......Page 58
4.5.1. Aufenkamp-Hohn-féle minimalizációs algoritmus......Page 63
4.5.2. Kiegészítés az Aufenkamp-Hohn minimalizációs algoritmushoz......Page 64
4.5.4. Kiegészítés az Aufenkamp-Hohn-féle minimalizációs algoritmus Moore-automatákhoz adaptált változatához......Page 70
4.5.5. Minimalizációs algoritmus kimenojel nélküli automatákra......Page 74
4.6. Automaták ekvivalenciája, Gill tétele......Page 75
4.8.1. Irányítható automaták......Page 77
4.8.3. Átlátszóbetus felismero automata......Page 78
4.9. Irodalmi megjegyzések......Page 79
5.1. Normálformák a reguláris nyelvtanokhoz......Page 80
5.2. Reguláris kifejezések......Page 82
5.2.1. Reguláris kifejezések ekvivalenciája......Page 84
5.2.3. Unió-normálforma reguláris kifejezésekhez......Page 86
5.3. Egyszeru szintaxis gráfok......Page 87
5.4. Véges elfogadó automaták (Rabin-Scott automaták)......Page 88
5.4.1. Véges determinisztikus és nemdeterminisztikus automaták ekvivalenciája......Page 92
5.4.2. Véges determinisztikus elfogadó automaták minimalizálása......Page 97
5.4.3. Véges automaták és reguláris nyelvtanok ekvivalenciája......Page 101
5.5. Nyelvek eloállítása automatákban......Page 108
5.6. Véges automaták analízise......Page 111
5.7. Véges automaták szintézise......Page 115
5.8. Véges automaták által indukálható leképezések......Page 118
5.9. Szóprobléma......Page 120
5.10. Iterációs lemma reguláris nyelvekre......Page 121
5.11. Zártsági tulajdonságok......Page 122
5.12. Irodalmi megjegyzések......Page 126
6.1. Normálforma......Page 128
6.2. 2-feju (véges állapotú) automata......Page 134
6.3. A szóprobléma megoldása......Page 138
6.4.1. Iterációs lemma......Page 141
6.4.2. Zártsági tulajdonságok......Page 142
6.5. Irodalmi megjegyzések......Page 143
7.1.1. A BNF megadási mód......Page 145
7.1.3. A szintaxis gráf......Page 146
7.2. Levezetési fa......Page 147
7.2.1. Többalakúság......Page 148
7.3.1. Chomsky-féle normálalak......Page 149
7.3.2. Greibach normálforma......Page 153
7.4. A Bar-Hillel lemma......Page 156
7.5. Veremautomaták......Page 161
7.6. Zártsági tulajdonságok......Page 179
7.7. A szóprobléma megoldása - szintaktikai elemzés......Page 180
7.7.1. A CYK algoritmus......Page 181
7.7.2. Az Earley-féle algoritmus......Page 187
7.8. Irodalmi megjegyzések......Page 193
8.2. Normálformák a környezetfüggo nyelvtanokhoz, a monoton és a környezetfüggo nyelvtanok ekvivalenciája......Page 195
8.3. Permutációs nyelvek......Page 201
8.4. Levezetési gráfok, levezetési fák a környezetfüggo nyelvtanokhoz......Page 202
8.5. Árnyék-veremautomata......Page 205
8.6. Lineárisan korlátozott automata......Page 207
8.7.1. A szóprobléma......Page 208
8.7.2. Zártsági tulajdonságok......Page 209
8.9. Irodalmi megjegyzések......Page 210
9.1. A Turing-gép......Page 211
9.2. A Turing-gépek megállási problémája és az algoritmikusan eldönthetetlen feladatosztályok kapcsolata......Page 220
9.2.1. Univerzális Turing-gép......Page 221
9.3. A szóprobléma - rekurzív és rekurzívan felsorolható nyelvek......Page 223
9.3.1. Bonyolultsági osztályok......Page 225
9.3.1.1. Egy NP-teljes probléma: a SAT......Page 226
9.4. Normálformák a mondatszerkezetu nyelvtanokhoz......Page 227
9.4.2. Geffert-féle normálformák......Page 228
9.5. Zártsági tulajdonságok......Page 229
9.6. Irodalmi megjegyzések......Page 230
10.1. Nyelvtanok kooperatív elosztott rendszerei – CD nyelvtanrendszerek......Page 231
10.2. Nyelvtanok párhuzamos kommunikáló rendszerei – PC nyelvtanrendszerek......Page 233
10.3. Irodalmi megjegyzések......Page 235
11. fejezet - Irodalomjegyzék......Page 236