Formálne jazyky a automaty

automaty

formálne jazyky

gramatiky

algoritmy

prázdne slovo

• 1. Jazyky a ich reprezentácia 1
  1.1. Abecedy a jazyky 1
  1.2. Procedúry a algoritmy 1
  1.3. Reprezentácia jazykov 3
  2. Gramatiky 5
  2.1. Úvod 5
  2.2. Formálny pojem gramatiky 6
  2.3. Typy gramatík 8
  2.4. Prázdne slovo 10
  2.5. Rekurzivita kontextových gramatík 12
  3. Konečné automaty a regulárne gramatiky 19
  3.1. Konečný automat 19
  3.2. Relácie ekvivalencie a konečné automaty 21
  3.3. Nedeterministické konečné automaty 23
  3.4. Konečné automaty a jazyky typu 3 26
  3.5. Vlastnosti jazykov typu 3 29
  3.6. Rozhodnuteľné problémy z oblasti konečných automatov 31
  3.7. Dvojsmerné konečné automaty 33
  4. Bezkontextové gramatiky 34
  4.1. Zjednodušenie bezkontextových gramatík 34
  4.2. Chomského normálny tvar 38
  4.3. Stromy odvodenia a ľavorekurzívne gramatiky 41
  4.4. Greibachovej normálny tvar 44
  4.5. Rozhodnuteľnosť problému konečnosti jazyka a veta uvwxy 47
  4.6. Zvláštne typy bezkontextových gramatík a jazykov 51
  5. Zásobníkové automaty 53
  5.1. Defínicia a príklady k zásobníkovým automatom 53
  5.2. Kontextové jazyky a nedeterministické zásobníkové automaty 59
  6. Deterministické zásobníkové automaty 64
  6.1. Gramatiky LR (k) 64
  7. Precedenčné gramatiky 75
  8. Turingove stroje 88
  8.1. Turingov stroj - základný model 88
  8.2. Turingove stroje a jazyky typu 0 91
  8.3. Lineárne ohraničené automaty a kontextové jazyky 92
  8.4. Nerozhodnuteľnosť problému zastavenia 92
  8.5. Postov korešpondenčný problém 93