IB005 Formální jazyky a automaty

Fakulta informatiky
jaro 2023
Rozsah
2/2/1. 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í)
Mgr. Paulína Ayaziová (cvičící)
Mgr. Tomáš Foltýnek, Ph.D. (cvičící)
Mgr. Marek Jankola (cvičící)
Bc. Tereza Kinská (cvičící)
RNDr. David Klaška (cvičící)
Mgr. Tomáš Macháček (cvičící)
Mgr. Juraj Major (cvičící)
Mgr. Tereza Schwarzová (cvičící)
prof. RNDr. Jan Strejček, Ph.D. (cvičící)
Bc. Adéla Štěpková (cvičící)
RNDr. Martin Jonáš, Ph.D. (pomocník)
Mgr. Anna Řechtáčková (pomocník)
prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D. (pomocník)
Mgr. Michael Koudela (pomocník)
Petra Ludvová Hašková, DiS. (pomocník)
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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
St 15. 2. až St 10. 5. St 10:00–11:50 D1
  • Rozvrh seminárních/paralelních skupin:
IB005/A: St 15. 2. až St 10. 5. St 14:00–15:50 A320, D. Klaška
IB005/01: Čt 16. 2. až Čt 11. 5. Čt 12:00–13:50 A320, J. Strejček
IB005/02: Čt 16. 2. až Čt 11. 5. Čt 18:00–19:50 B410, T. Kinská
IB005/03: Čt 16. 2. až Čt 11. 5. Čt 16:00–17:50 B411, T. Foltýnek
IB005/04: Čt 16. 2. až Čt 11. 5. Čt 14:00–15:50 B411, T. Foltýnek
IB005/05: St 15. 2. až St 10. 5. St 18:00–19:50 A320, A. Štěpková
IB005/06: Út 14. 2. až Út 9. 5. Út 14:00–15:50 A320, M. Jankola
Předpoklady
IB000 Mat. základy informatiky && ! IB102 Automaty a gramatiky
Znalost problematiky v rozsahu předmětu IB000 Matematické základy informatiky
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
Cíle předmětu
Kurs by měl u studenta rozvinout schopnost abstrakce, seznámit ho s možnostmi konečné specifikace nekonečných objektů, zde konkrétně jazyků, a naučit se aktivně pracovat se základními abstraktn9mi výpočetními modely a vytvořit předpoklady pro schopnosti vlastní formulace abstrakcí a jejich porozumění.
Výstupy z učení
Na konci tohoto kurzu bude student schopen:
Prokázat hluboké porozumění konceptům a technikám teorie automatů a jejich vztah k výpočtům.
Navrhnout abstraktní stroje modelující reálné systémy a specifikovat chování těchto strojů. Analyzovat výpočetní sílu těchto strojů
Porozumět pojmu vyčíslitelnosti na úrovni různých typů automatů a demostrovat jejicvh vlastnosti
Aplikovat tuto teorii v běžné informatické praxi a při návrhu relevatních softwarových systémů.
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 (TS). Rekursivní a rekursivně vyčíslitelné jazyky a funkce, uzávěrové vlastnosti. Lineárně ohraničené automaty.
  • Nerozhodnutelnost, problém zastavení TS, princip redukce, Postův korespondenční problém, nerozhodnutelné problémy z teorie jazyků.
Literatura
    neurčeno
  • HOPCROFT, John E., Rajeev MOTWANI a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. 3rd ed. Boston: Pearson/Addison Wesley, 2007, xvii, 535. ISBN 0321455363. info
  • HOPCROFT, John E., Rajeev MOTWANI a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Third edition. Harlow: Pearson, 2014, ii, 488. ISBN 9781292039053. 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. 2nd ed. Boston: Thomson Course Technology, 2006, xix, 431. ISBN 0534950973. info
  • CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
Výukové metody
přednášky, cvičení, samostudium a domácí úlohy.
Metody hodnocení
Domácí úlohy, jejiž hodnocení se započítává do konečného hodnocení. Závěrečná písemná zkouška bez pomocných materiálů.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/usr/kretinsky/fja1.html
Další komentáře
Studijní materiály
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 2003, 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 2024, jaro 2025.