Hlavní stránka

Teorie jazyků a automatů II, Základy teoretické informatiky II

Kódy:

Vyučován v zimním semestru 2017/18

Přednáška čtvrtek 3.-4. hodina (9:45-11:15), učebna B4
Cvičení podle domluvy čtvrtek 5.-6. hodina (11:25-12:55) nebo 11.-12. hodina (16:25-17:55), učebna B2 nebo B4

Požadavky

Zápočet:
  • Dvě zápočtové písemky, z každé je třeba získat nejméně 50 % bodů.
  • Pokud pořád nerozumíte učivu, tak se stavte na konzultaci (domluvte se mailem na konkrétní dobu)!
  • Témata pro zápočtový test č. 1:
    • Uzávěrové vlastnosti konečných automatů - zrcadlový obraz, průnik, rozdíl (sestrojte KA takový, že...)
    • Pumping lemma pro regulární jazyky (dokažte pomocí PM, že jazyk ... není regulární)
    • Minimalizace KA (k danému KA sestrojte ekvivalentní minimální)
    • Sestrojení regulárního výrazu podle KA
  • Témata pro zápočtový test č. 2:
    • Zadanou bezkontextovou gramatiku převeďte do tvaru gramatiky nezkracující, redukované, bez jednoduchých pravidel
    • Odstranění přímé levé (nebo pravé) rekurze v bezkontextové gramatice
    • Převod bezkontextové gramatiky do Chomského/Greibachové normální formy
    • Uzávěrové vlastnosti bezkontextových jazyků - sestrojte gramatiku, která generuje sjednocení/zřetězení/iteraci/reverzi...
    • Pumping lemma pro bezkontextové jazyky (dokažte, že jazyk ... není bezkontextový)
    • Sestrojte zásobníkový automat pro jazyk...
    • Je dán zásobníkový automat končící s prázdným zásobníkem. Sestrojte ekvivalentní ZA končící v koncovém stavu. A naopak
    • Podle zadané bezkontextové gramatiky sestrojte ekvivalentní zásobníkový automat
    • Sestrojte Turingův stroj pro jazyk (bude to některý z těch tří jazyků, které jsou řešeny ve sbírce příkladů v kapitole 4)
    • Kurodova normální forma (stačí pouze pro gramatiky typu 1, ať nemusíme řešit případy, kdy je levá strana pravidla delší než pravá)
    Na písemce obvykle bývají buď přímo příklady ze sbírky příkladů nebo skript pro přednášky, nebo velmi podobné. Tedy si ve vlastním zájmu dotyčné soubory důkladně projděte. Protože se témata přesouvají mezi "prvním" a "druhým" pokračováním tohoto předmětu, mohou být některé příklady ze sbírky příkladů pro předchozí semestr.
  • [PDF] Výsledky pro rok 2017/18
Zkouška: Písemná zkouška, [PDF] seznam možných otázek ke zkoušce na rok 2015/16.

Materiály

Skripta k přednáškám

[PDF] Skripta - verze pro akademický rok 2015/16

Sbírka příkladů

[PDF], [ZIP] Sbírka příkladů pro cvičení, verze pro rok 2016/17.

Literatura

DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990.
CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984.
MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: ALFA 1987.
GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997.
HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: ALFA, 1987.
MEDUNA, A. Gramatiky, automaty a kompilátory. Brno: VUT, 1987.

Zdroje na Internetu:

www.cis.upenn.edu/~cis511/
www.cs.vsb.cz/jancar/TJAA/tjaa.htm
www.fit.vutbr.cz/study/courses/TI1/public/Texty/ti.pdf
www1.osu.cz/home/Habibal/dizertace/texty/ytzi1.pdf
www.fi.muni.cz/usr/kretinsky/fja1.html
www.fi.muni.cz/usr/kretinsky/fja2.html
www.cs.cas.cz/~savicky/vyuka/fja/texty.html
kti.mff.cuni.cz/downloads/Automstr_ps.zip
www.jikos.cz/~mira/ref/PrInf/PReferat.html
pes.internet.cz/veda/clanky/6169_48_0_0.html
fimuni.org
obraz.prague-golem.cz/clanek.asp?clanek=49&rubrika=23