Teorie jazyků a automatů II / Základy teoretické informatiky II
doc. RNDr. Lucie Ciencialová, Ph.D.
Teorie jazyků a automatů II / Základy teoretické informatiky II

Cíle výuky

Přecházíme ke složitějším teoretickým modelům struktur a postupů, tedy zásobníkovým automatům, Turingovým strojům a složitějším formám gramatik. 

Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášky.

Tento předmět je zaměřen na teoretickou informatiku, ale vždy mějte na paměti, že vše, co probíráme, má také využití v praxi (zejména při programování). Ve výuce jsou studenti u konkrétních témat upozorňováni na jejich praktické využití, také se s tématy mohou setkat v jiných předmětech. Například v předmětu Programování stavíme na strukturách konečných a zásobníkových automatů a regulárních a bezkontextových gramatik, upravujeme je a učíme se využívat je při zpracování strukturovaného textu typu zdrojového kódu programovacího jazyka, HTML (apod.) kódu webové stránky ve webovém prohlížeči, atd.

Osnova

  1. Opakování – konečné automaty a regulární gramatiky. Kritéria regulárnosti jazyka.
  2. Transformace bezkontextových gramatik. Kritéria bezkontextovosti.
  3. Zásobníkové automaty, varianty, typy akceptování.
  4. Uzávěrové vlastnosti bezkontextových jazyků.
  5. Deterministické bezkontextové jazyky.
  6. Gramatiky typu 0, Turingovy stroje.
  7. Gramatiky typu 1, Lineárně ohraničené automaty.
  8. Gramatiky a gramatické systémy neodpovídající Chomského hierarchii.


Chapter contains:
2
PDF
1
Study text
Previous