IB005 Formální jazyky a automaty
Fakulta informatikyjaro 2024
- Rozsah
- 2/2/1. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučováno prezenčně. - Vyučující
- prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D. (přednášející)
Petra Ludvová Hašková, DiS. (pomocník) - Garance
- prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D.
Katedra teorie programování - Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování - Fakulta informatiky - 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
- předmět má 56 mateřských oborů, zobrazit
- 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
- Č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
- 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
- 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
- SIPSER, Michael. Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 2006. xix, 431. ISBN 0534950973. 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
- Předmět je vyučován každoročně.
Výuka probíhá každý týden. - Nachází se v prerekvizitách jiných předmětů
- Statistika zápisu (nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2024/IB005