Automaták és formális nyelvek

Előszó 1
I. Klasszikus automaták,reguláris és környezetfüggetlen nyelvek 3
1. Előkészületek 7
    1.1 Halmazelméleti alapfogalmak és jelölések 7
    1.2 Nyelvek 9
    1.3 Generatív nyelvtanok 9
2 Reguláris nyelvek 13
    2.1 Félautomaták és automaták 13
    2.2 A reguláris és a felismerhető nyelvek kapcsolata 21
    2.3 A felismerhető nyelvek egy félcsoportelmélet jellemzése 24
    2.4 Eldönthetőségi kérdések 25
    2.5 Műveletek felismerhető nyelveken 27
    2.6 Reguláris kifejezések 29
    2.7 Redukált automaták 32
    2.8 Automaták minimalizálása 36
3 Szekvenciális gépek 41
    3.1 Mealy- és Moore-gépek 41
    3.2 Gépek által indukált leképezések 44
    3.3 Gépek ekvivalenciája 46
    3.4 Gépek minimalizálása 49
    3.5 A gépek által indukált leképezések és felismerhető nyelvek közti kapcsolat 51
4 Kompozíció és dekompozíció 55
    4.1 Alapfogalmak 55
    4.2 Az izomorfan és homomorfan teljes rendszerek jellmzése 58
5 Környezetfüggetlen nyelvek 61
    5.1 Derivációs fák 61
    5.2 Üres szó mentes nyelvtanok 66
    5.3 Redukált nyelvtanok 69
    5.4 Chomsky-féle normálalak 73
    5.5 Greibach-féle normálalak 79
    5.6 Eldöntési problémák 92
    5.7 Parikh-függvények 95
    5.8 Veremautomaták 100
    5.9 Zártsági tulajdonságok 117
    5.10 Determinisztikus nyelvek 120
    5.11 LL(k) és LR(k) nyelvtanok 129
II. Faautomaták és fatranszformátorok 141
6 Faautomaták 145
    6.1 Algebrai előkészületek 145
    6.2 Fák és erdők 151
    6.3 Faautomaták 153
    6.4 Boole-féle műveletek erdőkön 154
    6.5 Eldönthetőségi kérdések 155
    6.6 Nemdeterminisztikus faautomaták és nemdeterminisztikus felszálló automaták 157
    6.7 Determinisztikus felszálló faautomaták 163
    6.8 Reguláris fanyelvtanok 166
    6.9 xi-szorzat és xi-iteráció 170
    6.10 Reguláris kifejezések 173
    6.11 A faautomaták minimalizálása 177
    6.12 Lokális erdők 184
    6.13 Projekciók 186
    6.14 A faautomaták és a környezetfüggetlen nyelvek kapcsolata 191
    6.15 A faautomaták egy alkalmazása a környezetfüggetlen nyelvekre 196
7 Fatranszformátorok 199
    7.1 A fatranszformátorok két alaptípusa 200
    7.2 Fatranszformátorok speciális osztályai 206
    7.3 Fatranszformációk kompozíciói 211
    7.4 Felületi erdők 222
    7.5 Reguláris szűkítésű F-transzformátorok 233
    7.6 Általánosított szintaxis-vezérelt fordítók 236
Irodalomjegyzék 239
Tárgymutató 241