Matfyz Wiki
Zkouška se skládá ze dvou částí: online moodle test a ústní zkouška.
online moodle test
Test je složen z 12 otázek, které se typově ptají na znění definice a vět, vlastnosti určitých automatů a gramatik. Otázky jsou velice podobné minitestíkům, které jsou na moodlu. Pokud si projdete všechny minitestíky, tak pak je moodle test celkem jednoduchý. V příloze jsou otázky z moodle testu a všechny otázky z minitestíků.
ústní zkouška
Vytáhnete si jednu otázku na kterou máte 10-15 minut na přípravu a potom s vámi diskutuje řešení. Pokud nevíte, tak vám poradí/naznačí postup. Je velice na zkoušce velice hodná a milá.
Otázky, které jsem nashromáždil:
doplněk v deterministickém CFL
urči rozdíly mezi jazyky $L1 = \{w2w| w \in \{0,1\}^}$ a $L2 = {w2w^R|w \in {0,1}^}$
urči rozdíly mezi jazyky $L1 = \{ww^R| w \in \{0,1\}^}$ a $L2 = {w2w^R|w \in {0,1}^}$
zařaď jazyk do Chomského hierarchie + gramatiku jazyka L + lemma o vkládání
zařaď jazyk do Chomského hierarchie + napiš k němu LBA + převod LBA do gramatiky
převod kontextová gramatika - lineárně omezený TM
bezkontextové jazyky - napiš vše co víš + důkaz věty, kterou vybrala
uzávěrové vlastnosti CFL, sjednocení konkatenace iterace + důkaz pro homomorfizmus a inverzní homomorfizmus
zařaď jazyk do Chomského hierarchie + pumping lemma + příklad jazyka, který je pumpovatelný, ale není CFL
porovnat nedeterministický zásobníkový automat s přijímacím stavem a s prázdným zásobníkem + PL pro CFL
zařaď jazyky $L1 = \{ww| w \in \{0,1\}^}$ a $L2 = {wXw|w \in {0,1}^}$, kde X je pismeno, které nepatří do abecedy
CF jazyky uzavřenost na sjednocení, průnik, doplněk
Srovnat sílu DFA vs NFA
pumping lemma pro regulární jazyky (znění + důkaz) + příklad pumpovatelného ale neregulárního jazyka a důkaz neregularity
determinizace nedeterministického turingova stroje (tato otázka je nejspíše již vyřazená)
Attachments: