FI:I005 FJA I - Informace o předmětu

I005 Formální jazyky a automaty I

Rozsah

3/1. 4 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)

Klíčová témata

• • 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 1997, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/leto1997/I005