Formální jazyky a automaty

Anotace

V přednášce jsou zavedeny: bezkontextová a kontextová gramatika, Turingův stroj, zásobníkový a konečný automat, random access machine, booleovské obvody. Jsou ukázány některé převoditelnosti mezi těmito modely a jejich důsledky.

Sylabus

  1. Konečná abeceda, slovo, jazyk, třída jazyků, konečná reprezentace jazyka.
  2. Přepisovací systémy, bezkontextová a kontextová gramatika.
  3. Automaty obecně, Turingův stroj, zásobníkový automat.
  4. Příklad jazyka s logaritmickou prostorovou složitostí.
  5. Konečný automat, regulární výraz, přechodový diagram, jejich vzájemná ekvivalence.
  6. Každý regulární jazyk je bezkontextový, uzavřenost bezkontextových jazyků na sjednocení, zřetězení a iteraci.
  7. Nevypouštějící gramatika, Chomského normální forma.
  8. Věta o nahrazení, příklad jazyka, který není bezkontextový.
  9. Postův korespondenční problém, algoritmická nerozhodnutelnnost neprázdnosti průniku dvou bezkontextových jazyků.
  10. Random access machine.
  11. Vzájemné simulace jedno a vícepáskového TS a RAM.