Obsah: // L Konečný automat a jazyky rozpoznatelné konečným automatem...7 // 1.1. Intuitivní pojem jazyka a gramatiky...7 // 1.2. Teorie formálních jazyku...9 // 1.3. Účel teorie a její vlastnosti...10 // 1.4. Základní pojmy teorie jazyků...11 // 1.5. Konečný automat...13 // Z Deterministické a nedeterministické konečné automaty...27 // 2.1. Konstrukce automatu pro zadané jazyky...27 // 2.2. Algoritmus převodu NKA na DKA - stromový algoritmus...30 // 2.3. Vztah jazyku rozpoznatelných NKA a DKA...34 // 2.4. Ekvivalentní automaty...37 // T Zobecněné NKA a třída jazyků rozpoznatelných KA...40 // 3.1. Zobecněný nedeterministický automat...40 // 3.2. Převod ZNKA přímo na DKA...43 // A Uzávěrové vlastnosti třídy jazyků rozpoznatelných KA...45 // 4.1. Sestrojování automatů pro sjednocení, průnik, doplněk, rozdíl, // zrcadlový obraz...46 // 4.2. Uzávěrové vlastnosti třídy jazyků rozpoznatelných konečnými // automaty...54 // 4.3. Zřetězení, mocnina, iterace, zrcadlový obraz a kvocient.57 // 4.4. Konstrukce používané v důkazech...62 // 5. Regulární jazyky a regulární výrazy...68 // 5.1. Regulární jazyky a výrazy...69 // 5.2. Sestrojení automatu (ZNKA) ? regulárnímu výrazu...73 // 6 Charakterizace regulárních jazyků pomocí pravých kongruencí..78 // 6.1. Pravá kongruence a Nerodova věta...78 // 6.2. Aplikace Nerodovy věty...81 // 7. Algoritmus redukce KA. ekvivalence KA...84 // 7.1. Algoritmus redukce...84
// 7.2. Příklady redukce a normování...90 // ? Bezkontextové gramatiky a jazyky, regulární gramatiky...97 // 8.1. Bezkontextová gramatika a bezkontextový jazyk...98 // 8.2. Tvorba gramatik ? bezkontextovým jazykům...100 // 8.3. Regulární gramatiky, vztah ? regulárním jazykům...102 // 9 Nevypouštějící a redukované gramatiky...108 // 9.1. Nevypouštějící gramatiky...108 // 9.2. Převody na nevypouštějící a redukované tvary...110 // 10. Kanonická odvození, jednoznačné gramatiky...113 // 10.1. Kanonické derivace a nejednoznačnost...113 // 11. Normální formy, lemma o vkládání...115 // 11.1. Chomského normální forma a pumping lemma...115 // 11.2. Greibachové normální forma...118 // 12. Zásobníkové automaty...124 // 12.1. Zásobníkový automat a vztah k BKJ...125 // 13. Vlastnosti tříd bezkontextových jazyků...131 // 13.1. Uzávěrové vlastnosti třídy BKJ...131 // 14. Chomského hierarchie...133 // 14.1. Obecná generativní gramatika a Chomského hierarchie...134 // 14.2. Turingův stroj...135 // 2