Formální jazyky a automaty

Přednáška probíhá na katedře logiky FF UK.

ZS 2/0 Zk

Sylabus
Průběh ZS 2016/2017
Průběhy předchozích ročníků

Texty k přednášce

Úvod, regulární a bezkontextové jazyky

jedna strana na jeden list   fja2016AutGr1.pdf
dvě strany na jeden list fja2016AutGr2.pdf

Příklady algoritmicky nerozhodnutelných úloh

jedna strana na jeden list   fja2016AN.pdf

Odkazy

Na Wikipedii lze nalézt doplňující články k probíraným pojmům, například
Finite-state machine
Context-free grammar
LR parser
GLR parser
CYK algorithm

Konzultace a zkoušky

Konzultaci je možné domluvit emailem a přihlásit se ke zkoušce je také možné emailem.

Literatura

Ke zkoušce jsou k bodům 1 - 9 sylabu postačující výše uvedené učební texty a pro body 10 a 11 jsou postačující
sekce 2.2.2 z textu pro výpočetní složitost I
sekce 3 z textu pro výpočetní složitost II
ze stránky předmětu výpočetní složitost.

Pro doplnění lze využít následující

  1. J. E. Hopcroft, J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Company, 1979.
  2. M. Chytil, Automaty a gramatiky, Matematicky seminar SNTL, 1984.
  3. G. Rozenberg, A. Salomaa, Handbook of Formal Languages, Springer-Verlag Berlin/Heidelberg 1999.