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
    • Zadanou bezkontextovou gramatiku převeďte do tvaru gramatiky nezkracující, redukované, bez jednoduchých pravidel
  • Témata pro zápočtový test č. 2:
    • 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
    • Pumping lemma pro bezkontextové jazyky (dokažte, že jazyk ... není bezkontextový)
    • Sestrojte zásobníkový automat pro jazyk...
    • Kurodova normální forma pro gramatiky typu 0
    • Převod nezkracující gramatiky typu 1 na kontextovou
    • Kurodova normální forma pro gramatiky typu 1 (pozor, výsledek musí být nezkracující, takže žádné epsilony apod.)
    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.
  • [HTML] Hodnocení zkoušek

Materiály

Skripta k přednáškám

[PDF] Skripta - verze pro akademický rok 2015/16
[PDF] Prezentace pro úvod do jazyků typu 0 (je tam i převod gramatiky typu 0 do KNF)
[PDF] Prezentace pro jazyky typu 1 (je tam i převod gramatiky typu 1 do KNF)

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