IB005 Formální jazyky a automaty I

Fakulta informatiky
jaro 2003
Rozsah
2/2. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučující
prof. RNDr. Mojmír Křetínský, CSc. (přednášející), prof. RNDr. Ivana Černá, CSc. (zástupce)
prof. RNDr. Ivana Černá, CSc. (cvičí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í)
doc. Mgr. Radek Pelánek, Ph.D. (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. Mojmír Křetínský, CSc.
Rozvrh seminárních/paralelních skupin
IB005/01: Čt 13:00–14:50 B003, J. Barnat
IB005/02: Čt 15:00–16:50 B003, J. Barnat
IB005/03: Čt 13:00–14:50 B007, V. Řehák
IB005/04: St 9:00–10:50 B204, V. Řehák
IB005/05: Čt 9:00–10:50 B011, R. Rožník
IB005/06: Čt 11:00–12:50 B011, R. Rožník
IB005/07: Čt 13:00–14:50 B011, O. Stražovský
IB005/08: Pá 8:00–9:50 B204, R. Pelánek
IB005/09: Čt 9:00–10:50 B003, P. Moravec
IB005/10: Čt 15:00–16:50 B007, T. Brázdil
IB005/11: Čt 11:00–12:50 B007, J. Holeček
IB005/12: Čt 9:00–10:50 B007, P. Šimeček
IB005/A: Čt 11:00–12:50 B003, I. Černá
IB005/St: St 13:00–15:50 D1, M. Křetínský
Předpoklady
! I005 FJA I &&! I505 FJA I && ( MB005 Základy matematiky || M005 Základy matematiky )&& ! IB102 Automaty a gramatiky
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 klasické základní výpočetní modely. Vytvořit předpoklady pro schopnosti vlastní fomulace abstrakcí a jejich porozumění.
Osnova
  • Pojem jazyka a problém specifikace (nekonečných) jazyků; základní operace nad jazyky. Přepisovací systémy a gramatiky. Chomského hierarchie.
  • Konečné automaty a regulární gramatiky; Pumping lemma, Myhillova--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. Nástin aplikací (grep, ..., lex).
  • Bezkontextové gramatiky a jazyky; transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti; konečnost a regularita.
  • Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám; nedeterministická syntaktická analýza shora dolů a zdola nahoru.
  • Turingovy stroje. Rekursivní a rekursivně vyčíslitelné jazyky a funkce, uzávěrové vlastnosti. Lineárně ohraničené automaty.
  • Deterministické zásobníkové automaty a deterministické bezkontextové jazyky; vlastnosti. Nástin aplikací (deterministické analýza shora -- princip; zdola -- nástroj yacc/bison).
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
Metody hodnocení
2 písemné zkoušky během semestru a závěrečná písemná zkouška.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/usr/kretinsky/fja1.html
Další komentáře
Předmět je vyučován každoročně.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, jaro 2020, jaro 2021, jaro 2022, jaro 2023, jaro 2024, jaro 2025.