Hlavní stránka

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

Kódy:

Vyučován v letním semestru 2016/17

Přednáška úterý 3.-4. hodina (9:45-11:15), učebna B4
Cvičení úterý 9.-10. hodina (14:45-16:15), učebna B4

Požadavky

Zkouška:
  • Zkoušková písemka, později zde bude seznam okruhů (otázek). Následuje pohovor o těch částech písemné zkoušky, kde výsledky nebyly zcela jasné.
  • Zkouška může vypadat i podle toho, zda dotyčný student chodí či nechodí na přednášky. U často nepřítomných studentů budu předpokládat, že jsou v dané oblasti již prakticky odborníky, tedy si na zkoušce popovídáme na trochu vyšší úrovni.
  • [PDF] Seznam otázek ke zkoušce, rok 2016/17. Čtěte i upozornění na začátku souboru.
Zápočet:
  • Účast (aktivní) na cvičeních je pro studenty prezenčního studia povinná. Podrobnosti na cvičení.
  • Tři zápočtové písemky, z každé je třeba získat nejméně 50 % bodů.
  • U druhé a třetí písemky je třeba získat z každého příkladu alespoň jeden bod.
  • [PDF] ukázkový test č. 1, [PDF] jeho řešení
  • Test č. 2 (platí pro rok 2016/17):
    1. převod nedeterministického konečného automatu na ekvivalentní deterministický, zúplnění automatu (vytvoření ekvivalentního totálního)
    2. podle zadaného automatu zpracovat dané slovo (tj. posloupnost konfigurací)
    3. uzávěrové operace aplikované na automatech - sjednocení, zřetězení, iterace
    4. k uvedenému regulárnímu výrazu sestrojte ekvivalentní konečný automat (vytvořte dílčí automaty pro podvýrazy a pak je pospojujte postupy pro sjednocení, zřetězení, iteraci)
    5. redukce konečného automatu (odstranění nedosažitelných a nadbytečných stavů)
  • Test č. 3 (platí pro rok 2016/17):
    1. vytvoření regulární gramatiky podle jazyka
    2. vytvoření konečného automatu podle reg. gramatiky
    3. vytvoření reg. gramatiky podle konečného automatu (pozor - může být nutná předběžná úprava ohledně počátečního stavu a koncových stavů)
    4. vytvoření bezkontextové gramatiky podle jazyka
    5. derivační strom (v gramatice odvoďte dané slovo a k této derivaci vytvořte derivační strom)
    6. převod bezkontextové gramatiky na nezkracující (odstranění epsilon-pravidel)
    7. zásobníkový automat pro probírané jazyky
  • [PDF] ukázkový zápočtový test pro kombinované studium (shrnuje všechny tři prezenční testy), [PDF] jeho řešení
[PDF] výsledky všech písemek (rok 2016/17)

Materiály

Upozorňuji, že veškerá moje skripta jsou formátována dle typografických pravidel, což znamená, že pokud je chcete tisknout stylem "dvě stránky na jednu", měla by být titulní strana vpravo (tj. samotná na prvním papíru), aby číslování stránek bylo na vnějších okrajích dvojstran.

Sbírka příkladů ke cvičením

Skripta k přednáškám

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