Surynek 26. 05. 2015

Na začátku byla jedna otázka na zařazení jazyka co nejpřesněji do chomského hierarchie (určitě bylo víc verzí, nejspíš měl každý svůj jazyk). Potom byl jeden důkaz z přednášky. Kolik na to bylo času to nevím, ale probíhalo to tak, že kdo měl zařazenej ten jazyk tak mu to šel ukázat a dostal druhou otázku.

Já dostal $L = \{$kod(T)$| L(T) = \varnothing$ nad abecedou $\{0,1\}\}$ a Kleeneho větu.

Já jsem dostal $L = \{ a^ib^jc^k | i = j = k \}$ a pumping lemma pro regulární jazyky.

Kolega dostal $L = \{ a^p | p \text{ je prvo\v{c}\'{i}slo} \}$ a důkaz že lineárně omezené turingovy stroje přijímají právě kontextové jazyky.

$L = \{ucv| u,v \in \{a,b\}^* \& u e v \}$ a definice rekurzivních jazyků, pokud existuje jazyk, který není rekurzivní a důkaz, že není rekurzivní. (třeba $L_u$)

Já dostal zařadit L_u a potom Myhill-Nerodovu větu. Nejspíš jsem tak sklidil ty jednodušší.

Koukám že nemám moc velký paměťový rozsah co do definice L_u :). Ne L_u (tj. kde by se vyžadovalo, že TS jím kódovaný musí slovo přijímat), ale jazyky kódující TS lhostejno zda přijmou. Takže stačilo udělat konečný automat, který zvalidoval, že to je ve formátu co jsme měli na přednášce.