Teoretická informatika

teoretická informatika

skriptá

• 1 Úvod do informatiky 5
  1.1 Jazyky a automaty 6
  1.2 Modely algoritmov 7
  1.2.1 Rekurzívne schémy a funkcie 10
  1.2.2 Turingove stroje 13
  2 Motivačné zdroje informatiky 17
  2.1 Jazyky a ich reprezentácie 17
  2.1.1 Základné otázky o formálnych jazykoch 19
  2.1.2 Reprezentácia jazykov procedúrami 20
  2.2 Gramatiky a jazyky 27
  2.2.1 Formálne gramatiky 29
  2.2.2 Vybrané vlastnosti gramatík a jazykov 32
  3 Konečné automaty 37
  3.1 Konečné automaty s výstupom 37
  3.1.1 Konečné automaty s výstupom Mealy 38
  3.1.2 Konečné automaty s výstupom Moore 43
  3.1.3 Podobnosť konečných automatov Moore a Mealy .47
  3.2 Ekvivalencia konečných automatov 54
  3.2.1 Ekvivalencia stavov v konečnom automate 54
  3.3 Konečno-stavové akceptory 66
  3.3.1 Nedeterministické konečno-stavové akceptory 68
  3.3.2 Determinizácia ndksa 69
  3.3.3 Determinizácia ndksa 72
  3.4 Regulárne gramatiky a konečno-stavové akceptory 75
  3.5 Analýza a syntéza ksa 78
  3.5.1 Regulárne výrazy 78
  3.5.2 Analýza ksa 81
  3.5.3 Syntéza ksa 90
  3.5.4 Vlastnosti regulárnych jazykov91
  3.5.5 Algoritmické problémy regulárnych jazykov 97
  4 Zásobníkové automaty a bezkontextové jazyky 99
  4.1 Zásobníkové automaty 99
  4.2 Bezkontextové gramatiky 105
  4.2.1 Chomskeho tvar bezkontextových gramatík 105
  4.2.2 Greibachovej tvar bezkontextových gramatík 109
  4.3 Jazyková ekvivalencia zásobníkových automatov a bezkontextových gramatík 117
  4.4 Niektoré vlastnosti jazykov 122
  4.4.1 Stromy odvodenia v bezkontextových gramatikách 122
  4.4.2 Vlastnosti bezkontextových jazykov 125
  5 ZBYTOK 129
  5.1 Uzáverové vlastnosti 129