CZV_VT007 Jazyky, automaty a gramatiky

Celouniverzitní studia
jaro 2001
Rozsah
0/0. Ukončení: k.
Vyučující
prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
prof. RNDr. Antonín Kučera, Ph.D. (přednášející)
Garance
prof. RNDr. Luděk Matyska, CSc.
Fakulta informatiky
Kontaktní osoba: prof. RNDr. Mojmír Křetínský, CSc.
Předpoklady
Základy teorie množin a logiky v rozsahu středoškolského učiva.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.

Předmět si smí zapsat nejvýše 50 stud.
Momentální stav registrace a zápisu: zapsáno: 0/50, pouze zareg.: 0/50
Mateřské obory/plány
Cíle předmětu
Pojem jazyka a gramatiky. Chomského hierarchie.
Regulární jazyk, konečný automat, minimalizace - Myhillova-Nerodova věta.
Nedeterministické konečné automaty, podmnožinová konstrukce; vztah ke gramatikám.
Regulární výrazy, vztah ke konečným automatům -- Kleeneho věta.
Aplikace regulárních jazyků.
Bezkontextové gramatiky a jazyky - aparát pro specifikaci syntaxe programovacích jazyků.
Transformace bezkontextových gramatik, normální formy. Vlastnosti bezkontext. jazyků.
Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám -- principy nedeterministické syntaktické analýzy.
Deterministické zásobníkové automaty a jejich aplikace: vybrané metody deterministické syntaktické analýzy -- LL(1) tabulkou a rekursivním sestupem.
Osnova
  • Pojem jazyka a gramatiky. Chomského hierarchie.
  • Regulární jazyk, konečný automat, minimalizace - Myhillova-Nerodova věta.
  • Nedeterministické konečné automaty, podmnožinová konstrukce; vztah ke gramatikám.
  • Regulární výrazy, vztah ke konečným automatům -- Kleeneho věta.
  • Aplikace regulárních jazyků.
  • Bezkontextové gramatiky a jazyky - aparát pro specifikaci syntaxe programovacích jazyků.
  • Transformace bezkontextových gramatik, normální formy. Vlastnosti bezkontext. jazyků.
  • Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám -- principy nedeterministické syntaktické analýzy.
  • Deterministické zásobníkové automaty a jejich aplikace: vybrané metody deterministické syntaktické analýzy -- LL(1) tabulkou a rekursivním sestupem.
Literatura
  • M.Křetínský, A.Kučera: Teoretické základy informatiky I - Automaty a gramatiky. Učební text FI MU, Brno 2001
  • CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
Metody hodnocení
Samostatné studium z učebního textu. Během semestru 2 soustředění - konzultace.
Hodnocení: 1-krát za 3 týdny zadány příklady k samostanému řešení a závěrečná písemná zkouška. Celkové hodnocení odvozeno z odevzdaných řešení zadaných příkladů a výsledku závěrečné písemné zkoušky.
Informace učitele
http://dist.fi.muni.cz-d007
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je vyučován jednorázově.
Poznámka k četnosti výuky: distanční formou.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/cus/jaro2001/CZV_VT007