IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2008
Rozsah
2/2. 4 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Jan Strejček, Ph.D. (přednášející)
RNDr. Tomáš Babiak, Ph.D. (cvičící)
RNDr. František Blahoudek, Ph.D. (cvičící)
RNDr. Václav Brožek, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
doc. RNDr. Milan Češka, Ph.D. (cvičící)
Bc. Tomáš Janoušek (cvičící)
doc. RNDr. Petr Novotný, Ph.D. (cvičící)
RNDr. Petr Ročkai, Ph.D. (cvičící)
RNDr. Mária Svoreňová, Ph.D. (cvičící)
Mgr. Bc. Martin Šmérek (cvičící)
RNDr. Jana Tůmová, Ph.D. (cvičící)
Mgr. et Mgr. Miroslav Cupák (pomocník)
RNDr. Jakub Chaloupka, Ph.D. (pomocník)
Mgr. Bohuslav Kabrda (pomocník)
Mgr. Martin Křivánek (pomocník)
Mgr. Lukáš Másilko (pomocník)
Mgr. Martin Milata (pomocník)
Mgr. Filip Štefaňák (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Jan Strejček, Ph.D.
Rozvrh
Po 10:00–11:50 D1, Po 10:00–11:50 D3
  • Rozvrh seminárních/paralelních skupin:
IB102/01: Út 16:00–17:50 B011, T. Babiak
IB102/02: Út 18:00–19:50 A107, T. Babiak
IB102/03: Po 12:00–13:50 B003, F. Blahoudek
IB102/04: Čt 8:00–9:50 B204, V. Brožek
IB102/05: Po 16:00–17:50 B204, M. Češka
IB102/06: Po 18:00–19:50 B204, M. Češka
IB102/07: Po 14:00–15:50 B011, T. Janoušek
IB102/08: Út 8:00–9:50 C511, P. Budíková
IB102/09: Pá 8:00–9:50 B410, P. Novotný
IB102/10: Čt 8:00–9:50 B011, P. Ročkai
IB102/11: St 14:00–15:50 B011, J. Strejček
IB102/12: Čt 12:00–13:50 B204, J. Strejček
IB102/13: Út 16:00–17:50 B003, M. Svoreňová
IB102/14: Pá 12:00–13:50 B011, M. Šmérek
IB102/15: St 12:00–13:50 B003, J. Tůmová
IB102/16: St 18:00–19:50 B410, J. Tůmová
Předpoklady
( MB101 Matematika I || MB005 Základy matematiky )&& ! IB005 FJA I
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 24 mateřských oborů, zobrazit
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ů.
  • Konečné automaty a regulární gramatiky: Pumping lemma, Nerodova věta, minimalizace, nedeterministické konečné automaty.
  • Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost.
  • 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.
Literatura
  • ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. URL 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
  • 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
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
Metody hodnocení
Přednášky a cvičení. Nepovinné domácí úkoly. Písemná zkouška během semestru a závěrečná písemná zkouška. Výsledky vnitrosemestrální písemky 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/~xstrejc/IB102/
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.