Formális Nyelvek és Automaták

Dömösi, Pál

Nyíregyházi Főiskola

Falucskai, János

Nyíregyházi Főiskola

Horváth, Géza

Debreceni Egyetem

Mecsei, Zoltán

Debreceni Egyetem

Nagy, Benedek

Debreceni Egyetem

Vaszil, György

Lektorálta 

Új Széchenyi Terv logó.

Tartalom

1. Bevezetés
2. Formális nyelvek
2.1. Ábécé, szó, formális nyelv, szabad monoid, szabad félcsoport
2.2. Nyelvműveletek
3. Formális rendszer és néhány főbb típusa
3.1. Markov-féle normál algoritmus
3.2. Generatív nyelvtan, Chomsky-féle nyelvosztályok
3.2.1. Chomsky-féle nyelvosztályok
3.2.2. A Chomsky hierarchia
3.3. L-rendszerek
3.4. Problémakörök
3.4.1. Normálformák (Normálalakok)
3.4.2. Levezetések szerkezete
3.4.3. A szóprobléma és a szintaktikai elemzés
3.4.4. Nyelvosztályok és automataosztályok kapcsolata
3.4.5. Nyelvosztályok tulajdonságai
3.4.6. Speciális alosztályok
4. A véges automaták elméletének alapjai
4.1. Az automata fogalma és főbb típusai
4.1.1. Mealy automata
4.1.2. Moore automata
4.1.3. Kimenőjel nélküli automata
4.1.4. Iniciális automata
4.1.5. Parciális és teljesen definiált automata
4.1.6. Nemdeterminisztikus és determinisztikus automata
4.1.7. Sztochasztikus automata
4.1.8. Rabin-Scott automata
4.2. Az automaták megadása
4.2.1. Véges automaták megadása Cayley táblázattal
4.2.2. Véges automaták megadása gráfokkal
4.3. Az automata, mint algebrai struktúra: részautomata, homomorfizmus, izomorfizmus, kompatibilis osztályozás
4.3.1. Mealy automata, mint algebrai struktúra
4.3.2. Moore automata, mint algebrai struktúra
4.3.3. Kimenőjel nélküli automata, mint algebrai struktúra
4.4. Az automaták által indukált leképezések
4.5. Redukált automata. Véges determinisztikus automaták minimalizálása
4.5.1. Aufenkamp-Hohn-féle minimalizációs algoritmus
4.5.2. Kiegészítés az Aufenkamp-Hohn minimalizációs algoritmushoz
4.5.3. Aufenkamp-Hohn féle minimalizációs algoritmus Moore-automatákhoz adaptált változata
4.5.4. Kiegészítés az Aufenkamp-Hohn-féle minimalizációs algoritmus Moore-automatákhoz adaptált változatához
4.5.5. Minimalizációs algoritmus kimenőjel nélküli automatákra
4.5.6. Kiegészítés a minimalizációs algoritmus kimenőjel nélküli automatákra ismertetett változatához
4.6. Automaták ekvivalenciája, Gill tétele
4.7. Automaták analízise és szintézise
4.8. Egyéb véges automaták
4.8.1. Irányítható automaták
4.8.2. Automata több kezdőállapottal
4.8.3. Átlátszóbetűs felismerő automata
4.9. Irodalmi megjegyzések
5. Reguláris nyelvek
5.1. Normálformák a reguláris nyelvtanokhoz
5.2. Reguláris kifejezések
5.2.1. Reguláris kifejezések ekvivalenciája
5.2.2. A kifejezésfa
5.2.3. Unió-normálforma reguláris kifejezésekhez
5.3. Egyszerű szintaxis gráfok
5.4. Véges elfogadó automaták (Rabin-Scott automaták)
5.4.1. Véges determinisztikus és nemdeterminisztikus automaták ekvivalenciája
5.4.2. Véges determinisztikus elfogadó automaták minimalizálása
5.4.3. Véges automaták és reguláris nyelvtanok ekvivalenciája
5.5. Nyelvek előállítása automatákban
5.6. Véges automaták analízise
5.7. Véges automaták szintézise
5.8. Véges automaták által indukálható leképezések
5.9. Szóprobléma
5.10. Iterációs lemma reguláris nyelvekre
5.11. Zártsági tulajdonságok
5.12. Irodalmi megjegyzések
6. Lineáris nyelvek
6.1. Normálforma
6.2. 2-fejű (véges állapotú) automata
6.3. A szóprobléma megoldása
6.4. A lineáris nyelvek tulajdonságai
6.4.1. Iterációs lemma
6.4.2. Zártsági tulajdonságok
6.5. Irodalmi megjegyzések
7. Környezetfüggetlen nyelvek
7.1. Programnyelvek szintaktikájának leírása
7.1.1. A BNF megadási mód
7.1.2. A COBOL-szerű megadási mód
7.1.3. A szintaxis gráf
7.1.4. A Hibrid megadási mód
7.2. Levezetési fa
7.2.1. Többalakúság
7.3. Normálformák a környezetfüggetlen nyelvtanokhoz
7.3.1. Chomsky-féle normálalak
7.3.2. Greibach normálforma
7.4. A Bar-Hillel lemma
7.5. Veremautomaták
7.6. Zártsági tulajdonságok
7.7. A szóprobléma megoldása - szintaktikai elemzés
7.7.1. A CYK algoritmus
7.7.2. Az Earley-féle algoritmus
7.8. Irodalmi megjegyzések
8. Környezetfüggő nyelvek
8.1. Szóhossznemcsökkentő (monoton) nyelvtanok
8.2. Normálformák a környezetfüggő nyelvtanokhoz, a monoton és a környezetfüggő nyelvtanok ekvivalenciája
8.3. Permutációs nyelvek
8.4. Levezetési gráfok, levezetési fák a környezetfüggő nyelvtanokhoz
8.4.1. Legbaloldalibb levezetés és átfogalmazása
8.5. Árnyék-veremautomata
8.6. Lineárisan korlátozott automata
8.7. A környezetfüggő nyelvek tulajdonságai
8.7.1. A szóprobléma
8.7.2. Zártsági tulajdonságok
8.8. Növekvő környezetfüggő nyelvek
8.9. Irodalmi megjegyzések
9. Rekurzívan felsorolható nyelvek és Turing-gépek
9.1. A Turing-gép
9.2. A Turing-gépek megállási problémája és az algoritmikusan eldönthetetlen feladatosztályok kapcsolata
9.2.1. Univerzális Turing-gép
9.3. A szóprobléma - rekurzív és rekurzívan felsorolható nyelvek
9.3.1. Bonyolultsági osztályok
9.4. Normálformák a mondatszerkezetű nyelvtanokhoz
9.4.1. Révész-féle normálalak
9.4.2. Geffert-féle normálformák
9.5. Zártsági tulajdonságok
9.6. Irodalmi megjegyzések
10. Nyelvtanrendszerek (Grammatikarendszerek)
10.1. Nyelvtanok kooperatív elosztott rendszerei – CD nyelvtanrendszerek
10.2. Nyelvtanok párhuzamos kommunikáló rendszerei – PC nyelvtanrendszerek
10.3. Irodalmi megjegyzések
11. Irodalomjegyzék

A példák listája

2.1. Szó hossza
2.2. Szavak egyenlősége
2.3. Véges és végtelen nyelvek
2.4. Szavak konkatenációja
2.5. Szavak konkatenációja egyelemű ábécé felett
2.6. Szó részszava
2.7. Nyelvműveletek - Gyakorló feladat
2.8. Nyelvek konkatenációja
2.9. Nyelvek számossága - Gyakorló feladat
2.10. Formális nyelvek, nyelvműveletek 1.feladat
2.11. Formális nyelvek, nyelvműveletek 2.feladat
3.1. Átírási rendszer
3.2. Levezetés átírási rendszerben
3.3. Generatív rendszer
3.4. Analitikus rendszer
3.5. Szemi-Thue rendszer
3.6. Elmélet teljessége, ellentmondásmentessége
3.7. Elemi helyettesítés
3.8. Unáris számok összeadása
3.9. Végtelen helyettesítési lánc
3.10. Unáris számok szorzása
3.11. Feladat - Legnagyobb közös osztó előállítása
3.12. Bináris szó rendezése
3.13. Bináris szó tükrözése
3.14. Bináris szó megegyező végeinek törlése
3.15. Bináris szám növelése 1-gyel
3.16. Unáris szám bináris alakja
3.17. Bináris szám csökkentése 1-gyel
3.18. Bináris szám unáris alakja
3.19. Generatív nyelvtan természetes nyelv "leírására"
3.20. Unáris négyzetszámok
3.21. Unáris prímszámok
3.22. Gyakorló feladat
3.23. Grammatikák főbb típusai 1. példa
3.24. Grammatikák főbb típusai 2. példa
3.25. Grammatikák főbb típusai 3. példa
3.26. Grammatikák főbb típusai 4. példa
3.27. Grammatikák főbb típusai 5. példa
3.28. Grammatikák főbb típusai 6. példa
3.29. Grammatikák főbb típusai 7. példa
3.30. Grammatikák főbb típusai 8. példa
3.31. Grammatikák főbb típusai 9. példa
3.32. Üresszó-lemma 1. feladat
3.33. Üresszó-lemma 2. feladat
3.34. Üresszó-lemma 3. feladat
3.35. Üresszó-lemma 4. feladat
3.36. Üresszó-lemma 5. feladat
3.37. Fibonacci szavak
3.38. Fraktálgenerálás L-rendszerrel
3.39. Kétdimenziós rajz L-rendszerrel
4.1. Automaták
4.2. Parciális automata
4.3. Nemdeterminisztikus automata
4.4. Rabin-Scott automata működés közben
4.5. A csengő, mint automata
4.6. Mealy és Moore automaták homomorfizmusa
4.7. Automataleképezések
4.8. Mealy-automata minimalizálása 1.feladat
4.9. Mealy-automata minimalizálása 2.feladat
4.10. Mealy-automata minimalizálása 3.feladat
4.11. Mealy-automata minimalizálása 4.feladat
4.12. Moore-automata minimalizálása 1.feladat
4.13. Moore-automata minimalizálása 2.feladat
4.14. Moore-automata minimalizálása 3.feladat
4.15. Átlátszóbetűs elfogadó automata
5.1. Végtelen reguláris nyelv
5.2. Nyelv megadása reguláris kifejezéssel 1. feladat
5.3. Nyelv megadása reguláris kifejezéssel 2. feladat
5.4. Nyelv megadása reguláris kifejezéssel 3. feladat
5.5. Nyelv megadása reguláris kifejezéssel 4. feladat
5.6. Nyelv megadása reguláris kifejezéssel 5. feladat
5.7. Nyelv megadása reguláris kifejezéssel 6. feladat
5.8. Reguláris kifejezés unió-normálformára alakítása - 1. feladat
5.9. Reguláris kifejezés unió-normálformára alakítása - 2. feladat
5.10. Reguláris kifejezés unió-normálformára alakítása - 3. feladat
5.11. Reguláris kifejezés unió-normálformára alakítása - 4. feladat
5.12. Reguláris kifejezés unió-normálformára alakítása - 5. feladat
5.13. Azonosítók nyelvének megadása szintaxis gráffal
5.14. Tizes számrendszerbeli egész számok nyelvének megadása szintaxis gráffal
5.15. Egész számok köznapi értelemben vett leírása - Gyakorló feladat
5.16. Egy nemdeterminisztikus véges automata
5.17. A páratlan a-ból és páros b-ből álló szavak nyelve
5.18. Az x-re végződő szavak nyelve
5.19. Automata determinizálása 1. feladat
5.20. Automata determinizálása 2. feladat
5.21. Automata determinizálása 3. feladat
5.22. Automata determinizálása 4. feladat
5.23. Automata determinizálása 5. feladat
5.24. Automata determinizálása 6. feladat
5.25. Automata determinizálása 7. feladat
5.26. Automata determinizálása 8. feladat
5.27. Véges elfogadó automata minimalizálása 1. feladat
5.28. Véges elfogadó automata minimalizálása 2. feladat
5.29. Véges elfogadó automata minimalizálása 3. feladat
5.30. Véges elfogadó automata minimalizálása 4. feladat
5.31. Ekvivalens reguláris nyelvtan megadása véges automatához 1. feladat
5.32. Ekvivalens reguláris nyelvtan megadása véges automatához 2. feladat
5.33. Ekvivalens reguláris nyelvtan megadása véges automatához 3. feladat
5.34. Ekvivalens reguláris nyelvtan megadása véges automatához 4. feladat
5.35. Ekvivalens véges automata megadása reguláris nyelvtanhoz 1. feladat
5.36. Ekvivalens véges automata megadása reguláris nyelvtanhoz 2. feladat
5.37. Ekvivalens véges automata megadása reguláris nyelvtanhoz 3. feladat
5.38. Ekvivalens véges automata megadása reguláris nyelvtanhoz 4. feladat
5.39. Ekvivalens véges automata megadása reguláris nyelvtanhoz 5. feladat
5.40. Ekvivalens véges automata megadása reguláris nyelvtanhoz 6. feladat
5.41. Ekvivalens véges automata megadása reguláris nyelvtanhoz 7. feladat
5.42. Egy véges automatával nem felismerhető nyelv
5.43. Ekvivalens reguláris kifejezés megadása véges automatához 1. feladat
5.44. Ekvivalens reguláris kifejezés megadása véges automatához 2. feladat
5.45. Ekvivalens reguláris kifejezés megadása véges automatához 3. feladat
5.46. Automata megadása reguláris kifejezéshez
5.47. Automata nyelvrendszer
5.48. Iterációs lemma alkalmazása
5.49. Reguláris nyelvtan megadása reguláris kifejezéshez 1. feladat
5.50. Reguláris nyelvtan megadása reguláris kifejezéshez 2. feladat
5.51. Reguláris nyelvtan megadása reguláris kifejezéshez 3. feladat
5.52. Reguláris nyelvtan megadása reguláris kifejezéshez 4. feladat
5.53. Reguláris nyelvtan megadása reguláris kifejezéshez 5. feladat
5.54. Reguláris nyelvtan megadása reguláris kifejezéshez 6. feladat
5.55. Reguláris nyelvtan megadása reguláris kifejezéshez 7. feladat
5.56. Reguláris nyelvtan megadása reguláris kifejezéshez 8. feladat
6.1. A kétbetűs ábécé feletti palindrómák (vagy tükörszavak) nyelvét generáló lineáris nyelvtan
6.2. 0 n 1 n nyelv - Gyakorló feladat
6.3. Erős lineáris normálalak 1. példa
6.4. Erős lineáris normálalak 2. feladat
6.5. Erős lineáris normálalak 3. feladat
6.6. Erős lineáris normálalak 4. feladat
6.7. Erős lineáris normálalak 5. feladat
6.8. Erős lineáris normálalak 6. feladat
6.9. Erős lineáris normálalak 7. feladat
6.10. Kétfejű automata készítése lineáris nyelvtanhoz
6.11. A szóprobléma megoldása lineáris nyelvekre 1.feladat
6.12. A szóprobléma megoldása lineáris nyelvekre 2.feladat
6.13. Lineáris iterációs lemma alkalmazása
6.14. Az akbkambm metalineáris nyelv
7.1. A számok jelölésére használható karaktersorozatok
7.2. A számok megadása COBOL-szerű módszerrel
7.3. Levezetési fa
7.4. Csellengő "else" feladat
7.5. Chomsky normálforma 1.feladat
7.6. Chomsky normálforma 2.feladat
7.7. Chomsky normálforma 3.feladat
7.8. Greibach normálforma 1.feladat
7.9. A Bar-Hillel lemma alkalmazása
7.10. Bar-Hillel lemma 1. feladat
7.11. Bar-Hillel lemma 2. feladat
7.12. Bar-Hillel lemma 3. feladat
7.13. Bar-Hillel lemma 4. feladat
7.14. Bar-Hillel lemma 5. feladat
7.15. Bar-Hillel lemma 6. feladat
7.16. Bar-Hillel lemma 7. feladat
7.17. Bar-Hillel lemma 8. feladat
7.18. Bar-Hillel lemma 9. feladat
7.19. Verem működése
7.20. Verem, mint rekurziós eszköz
7.21. Végállapottal elfogadó veremautomata működése
7.22. Az azonos számú a és b betűből álló szavakat végállapottal elfogadó veremautomata
7.23. A Dyck nyelvet végállapottal elfogadó automata
7.24. Állapotnélküli, üres veremmel elfogadó automata működése és a legbaloldalibb levezetés kapcsolata
7.25. Veremautomaták 1. feladat
7.26. Veremautomaták 2. feladat
7.27. Veremautomaták 3. feladat
7.28. Veremautomaták 4. feladat
7.29. Veremautomaták 5. feladat
7.30. Veremautomaták 6. feladat
7.31. Veremautomaták 7. feladat
7.32. Veremautomaták 8. feladat
7.33. Veremautomaták 9. feladat
7.34. A jelölt másolatok nyelvének komplementere - Gyakorló feladat
7.35. Cocke-Younger-Kasami algoritmus 1. feladat
7.36. Cocke-Younger-Kasami algoritmus 2. feladat
7.37. Cocke-Younger-Kasami algoritmus 3. feladat
7.38. Cocke-Younger-Kasami algoritmus 4. feladat
7.39. Earley algoritmus 1.feladat
7.40. Earley algoritmus 2. feladat
7.41. Earley algoritmus 3. feladat
7.42. Earley algoritmus 4. feladat
8.1. Monoton nyelvtan
8.2. Kuroda normálforma 1.feladat
8.3. Kuroda normálforma 2.feladat
8.4. Kuroda normálforma 3.feladat
8.5. Kuroda normálforma 4.feladat
8.6. Kuroda normálforma 5.feladat
8.7. Kuroda normálforma 6.feladat
8.8. Permutációs nyelvtan
8.9. Levezetési gráf monoton esetben
8.10. Levezetési gráf környezetfüggő nyelvtanban
8.11. Környezetfüggő levezetési fa
8.12. Árnyék-veremautomata és működése
8.13. Egy növekvő környezetfüggő nyelv
9.1. Turing gépek 1.feladat
9.2. Turing gépek 2.feladat
9.3. Turing gépek 3.feladat
9.4. Turing gépek 4. feladat
10.1. CD nyelvtanrendszer
10.2. CD nyelvtanrendszer
10.3. CD nyelvtanrendszerek - Gyakorló feladat
10.4. PC nyelvtanrendszer
10.5. PC nyelvtanrendszer gyakorló feladat