I005 Formální jazyky a automaty I
Fakulta informatikyléto 1998
- Rozsah
- 3/2. 5 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
- Vyučující
- prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
- Garance
- Kontaktní osoba: prof. RNDr. Mojmír Křetínský, CSc.
- Předpoklady
- Doporučeno absolvovat I000 Úvod do informatiky a M005 Základy matematiky
- 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
- Informatika (program FI, B-IN)
- Informatika (program FI, M-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
- Výpočetní technika (program FI, B-IN)
- Osnova
- Pojem jazyka a gramatiky. Chomského hierarchie.
- Konečné automaty a regulární gramatiky.
- Vlastnosti regulárních jazyků.
- Bezkontextové gramatiky a zásobníkové automaty.
- Vlastnosti bezkontextových jazyků.
- Deterministické zásobníkové automaty.
- Turingovy stroje. Vyčíslitelné jazyky a funkce.
- Nerozhodnutelnost, (parciální) rozhodnutelnost. Problém zastavení TS.
- Postův korespondenční problém. Algoritmicky nerozhodnutelné problémy z teorie jazyků.
- Statistika zápisu (léto 1998, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/leto1998/I005