BI-AAG – Automaty a gramatiky

Cíl předmětu

Studenti získají základní teoretické a implementační znalosti o konstrukci, použití a vzájemných transformací konečných automatů, regulárních výrazů a regulárních gramatik, o překladových konečných automatech a o konstrukci a použití zásobníkových automatů. Znají hierarchii formálních jazyků a rozumějí vztahům mezi formálními jazyky a automaty. Znalosti z teorie automatů umějí aplikovat pro řešení praktických problémů z oblasti vyhledávání v textu, kompresi dat, jednoduchých překladů a návrhu číslicových obvodů.

Program přednášek

  1. Motivace pro studium formálních jazyků. Základní pojmy (jazyk, abeceda, gramatika, automat), Chomského hierarchie.
  2. Deterministické a nedeterministické konečné automaty (DKA a NKA), NKA s epsilon přechody.
  3. Operace s automaty (převod na NKA bez epsilon přechodů, na DKA, minimalizace), průnik, sjednocení.
  4. Programová realizace DKA a NKA, obvodová realizace.
  5. Rozšíření o překlad, Mealey, Moore, převody.
  6. Operace s regulárními gramatikami, převody na KA.
  7. Regulární výrazy, převody mezi regulárními výrazy, konečnými automaty a regulárními gramatikami, Kleenova věta.
  8. Principy využití regulárních výrazů v UNIXu (grep, egrep, perl, PHP, ...).
  9. Konečný automat jako lexikální analyzátor, lex/flex generátory.
  10. Vlastnosti regulárních jazyků (pumping lemma, Nerodova věta).
  11. Jazyky bezkontextové, zasobníkový automat.
  12. Analýza bezkontextových jazyků (nedeterministická versus deterministická).
  13. Jazyky kontextové a neomezené, Turingův stroj.

Program cvičení

  1. Ukázky formálních jazyků. Intuitivní návrh gramatik pro jazyky zadané množinově. Odhad umístění jazyka v Chomského hierarchii.
  2. Intuitivní návrh konečných automatů (DKA, NKA, s epsilon-přechody) pro zadaný jazyk.
  3. Převody a kompozice KA.
  4. Implementace KA.
  5. Návrh KA s výstupní funkcí a jeho implementace.
  6. Převody gramatik na KA a zpět.
  7. Návrh, úpravy a převody regulárních výrazů.
  8. Využití regulárních výrazů pro řešení úloh ze zpracování textu (např. sh, grep, sed, perl).
  9. Návrh a implementace lexikálního analyzátoru.
  10. Klasifikace jazyků.
  11. Příklady bezkontextových jazyků, návrh zásobníkových automatů.
  12. Ukázky deterministické analýzy bezkontextových jazyků (např. LL, yacc, bison).
  13. Příklady kontextových a neomezených jazyků, návrh gramatik a Turingových strojů.



Poslední změna: 22.4.2009, 20:59