Automaták és formális nyelvek
HTML
Digitális Tankönyvtár
Szerző:
- Dömösi Pál Béla,
- Falucskai János,
- Horváth Géza,
- Mecsei Zoltán,
- Nagy Benedek;
Típus:
- jegyzet
Elektronizálás módja:
- Latex-PDF
Tervezett:
- 15 ív (DE – 12 ív, NyF – 3 ív)
Digitális elemek és számuk:
- 15 kép (DE – 12 kép, NyF – 3 kép)
Tartalom:
A tananyag felöleli az informatikai alapismeretek elsajátításához szükséges legfontosabb automataelméleti és formális nyelvészeti kutatási eredményeket és technológiákat.
Tartalomjegyzék:
Bevezetés
1. A formális rendszer fogalma és főbb típusai
1.1. Formális nyelv, szabad monoid, szabad félcsoport 1.2. Formális rendszer és néhány főbb típusal 1.3. Algoritmus, nyelvtan
2. Az automaták elméletének alapjai
2.1. Az automata fogalma és főbb típusai 2.2. Az automaták megadása 2.3. Az automata mint algebrai struktúra: részautomata, homomorfizmus, izomorfizmus, kompatibilis osztályozás 2.4. Az automaták által indukált leképezések 2.5. Redukált automata. Véges automaták minimalizálása 2.6. Automaták Ekvivalenciája, Gill Tétele 2.7. Reguláris Kifejezések 2.8. Automaták Analízise és Szintézise. Nyelvek Előállítása Automatákban 2.9. Véges Automaták Analízise 2.10. Véges Automaták Szintézise 2.11. Véges Automaták által Indukálható Leképezések
3. Formális Nyelvek: Definíciók és jelölések
3.1. Alapfogalmak 3.2. A Chomsky-féle nyelvosztályok 3.3. Nyelvekre értelmezett műveletek
4. Nyelvek és Automaták
4.1. Reguláris Nyelvtanok és Véges Automaták 4.2. Környezetfüggetlen Nyelvtanok és Veremutomaták 4.3. Mondatszerkezetű Nyelvek és a Turing-gépek 4.4. Környezetfüggő Nyelvek és a Lineárisan Korlátolt Automaták 4.5. A Turing-gépek megállási problémája és az algoritmikusan eldönthetetlen feladatosztályok kapcsolata
5. Környezetfüggetlen nyelvek
5.1. Chomsky-féle normál alak 5.2. Levezetési gráf 5.3. Lineáris grammatikák
6. Környezetfüggő nyelvek
7. Eldönthetőség
8. Véges Automaták, mint Lexikális Elemzők
8.1. Formális Nyelvek szintaktikus elemzése 9.1. A CYK algoritmus 9.2. Az Early-féle algoritmus 9.3. Bal- és jobboldali levezetések, levezetési fák 9.4. Környezetfüggetlen Nyelvtanok átalakításai 9.5. Felülről lefelé haladó elemzők 9.6. Alulról felfelé haladó elemzők
9. Függelék
Irodalom:
[1] A.V.Aho, Indexed Grammars - An Extension of Context-Free Grammars, Journ. of ACM, 15 (1968), 647-671.
[2] J. Dassow, M. Ito, G. Paun, On the Subword Density of Languages, SEA Bull. Math., 18 (1994), 49-61.
[3] T. Hayashi, On Derivation Trees of Indexed Grammars - An Extension of the uvwxy - Theorem, Publ. RIMS, Kyoto Univ., 9 (1973), 61-92.
[4] J.E. Hopcroft \& J. D. Ullmann, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading , Massachusetts, Menlo Park, California, London, Amsterdam, Don Mils,Ontario, Sidney, 1979.
[5] Gy.E. Révész, Introduction to Formal Languages, McGraw-Hill, New York, St Louis, San Francisco, Auckland, Bogota, Hamburg, Johannesburg, London, Madrid, Mexico, Montreal, New Delhi, Panama, Paris, Sao Paulo, Singapore, Sydney, Tokyo, Toronto, 1983.
[6] Salomaa, Formal Languages, Academic Press, New York, London,1973.
[7] H.J. Shyr, Free Monoids and Languages, National Chung-Hsing University, Taichung, Taiwan, R.O.C., Ho Min Book Company,1991.
Kurzus:
Automaták és formális nyelvek, Nyelvek és automaták