IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2003
Rozsah
2/2. 4 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
prof. RNDr. Jiří Barnat, Ph.D. (cvičící)
doc. RNDr. Tomáš Brázdil, Ph.D. (cvičící)
Mgr. Jan Holeček (cvičící)
Mgr. Pavel Moravec (cvičící)
Roman Rožník (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Oldřich Stražovský (cvičící)
RNDr. Pavel Šimeček, Ph.D. (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Rozvrh
Po 12:00–13:50 TA (Aula Technická)
  • Rozvrh seminárních/paralelních skupin:
IB102/01: Út 16:00–17:50 B204, J. Barnat
IB102/02: St 14:00–15:50 B011, P. Moravec
IB102/03: St 16:00–17:50 B011, J. Holeček
IB102/04: Po 14:00–15:50 B204, V. Řehák
IB102/05: Po 16:00–17:50 B204, V. Řehák
IB102/06: Čt 8:00–9:50 B003, P. Moravec
IB102/07: Čt 14:00–15:50 B003, T. Brázdil
IB102/08: St 8:00–9:50 B011, R. Rožník
IB102/09: St 10:00–11:50 B011, R. Rožník
IB102/10: Čt 14:00–15:50 B204, O. Stražovský
IB102/11: Pá 8:00–9:50 B204, P. Šimeček
Předpoklady
! I005 FJA I &&! I505 FJA I &&( MB101 Matematika I || MB005 Základy matematiky || M005 Základy matematiky )&& ! IB005 FJA I
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
Mateřské obory/plány
Cíle předmětu
Cíl: Rozvinout schopnost abstrakce, seznámit s možnostmi konečné specifikace nekonečných objektů, zde konkrétně jazyků, a studovat vybrané základní výpočetní modely. Vytvořit předpoklady pro schopnosti vlastní fomulace abstrakcí a jejich porozumění.
Osnova
  • Motivace - problém specifikace (nekonečných, regulárních) jazyků; základní operace nad jazyky.
  • Konečné automaty a regulární gramatiky; Pumping lemma, Nerodova věta, minimalizace. Nedeterministické konečné automaty, vztah k regulárním gramatikám.
  • Vlastnosti regulárních jazyků; uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost
  • Principy činnosti unixových programů grep, egrep,..., nástroj lex či ekvivalent.
  • Bezkontextové gramatiky a jazyky; transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti.
  • Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám; nedeterministická syntaktická analýza shora dolů a zdola nahoru.
  • Deterministické zásobníkové automaty, deterministická analýza: shora -- LL(1) gramatiky, zdola -- nástroj yacc či ekvivalent; (případové studie gramatik Java, C, ...).
Literatura
  • I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley Publishing Company, 1979, 418 s., ob. ISBN 0-201-02988-X. info
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987, 188 s. info
Metody hodnocení
Písemné zkoušky během semestru a závěrečná písemná zkouška. Výsledky vnitrosemestrálních písemek se započítávají do výsledného hodnocení. Všechny písemky bez pomocných materiálů.
Informace učitele
http://www.fi.muni.cz/usr/cerna/AaG/ib102.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.