Title: Točíme Maty

Jazyk rozpoznávaný automatem

Jazyk generovaný gramatikou

Regulární výrazy a vztah k regulárním jazykům

CFG (kontextfrei grammatik)

CFL: derivační strom

jednoznačnost/víceznačnost gramatiky

Chomského normální tvar gramatiky

Deterministické a nedeterministické zásobníkové automaty PDA (pushdown automaton)

L(P), N(P)

Bezprefixové jazyky

Rekurzivní a rekurzivně spočetné jazyky

Diagonální jazyk L_d = {w; TM s kódem w nepříjmá vstup w}

Univerzální jazyk (Univerzální Turingův stroj)

Třída časové složitosti P

Třída časové složitosti NP

Třída časové složitosti co - NP

NP-úplnost jazyka

Třída prostorové složitosti SPACE, NPSPACE

Mihyll-Nerodova věta

Pumping lemma pro regulární jazyky

Pumping lemma pro bezkontextové jazyky

Kleeneho věta (algebraická definice regulárních jazyků)

gramatiky typu 0

kontextové gramatiky, monotónní gramatiky

regulární gramatika

Turingovy stroje, vícepáskové, nedeterministické

lineárně omezené automaty

konečné automaty DFA, NFA, lambdaNFA

Nedeterminismus nutný u zásobníkových automatů a lineárně omezených automatů (u konečných automatů a TM ne)

uzávěrové vlastnosti - regulární jazyky

Uzávěrové vlastnosti regulárních a CFL jazyků na řetězcové operace

Cook-Levinova věta (3SAT je NP-úplný)

Dosažitelné stavy konečného automatu (FA)

Rozlišitelné a ekvivalentní stavy FA

Ekvivalence FA

Nalezení reduktu DFA

Podmnožinová konstrukce z NFA

Odstranění ne-generujících a ne-dosažitelných symbolů CFG gramatiky

Eliminace lambda pravidel CFG

Převod CFG na gramatiku v Chomského normální formě

CYK (slovo v CFL)

uzávěrové vlastnosti - CFL

uzávěrové vlastnosti - deterministické CFL