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
a
- urči rozdíly mezi jazyky
a
- 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
a
, 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á)
Zkouška se skládá ze dvou částí: online moodle test a ústní zkouška.
[u]online moodle test [/u]
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ů.
[u]ústní zkouška[/u]
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 [latex]L1 = \{w2w| w \in \{0,1\}^*\}[/latex] a [latex]L2 = \{w2w^R|w \in {0,1}^*\}[/latex]
- urči rozdíly mezi jazyky [latex]L1 = \{ww^R| w \in \{0,1\}^*\}[/latex] a [latex]L2 = \{w2w^R|w \in {0,1}^*\}[/latex]
- zařaď jazyk [latex]L = \{0^n1^n0^n\}[/latex] do Chomského hierarchie + gramatiku jazyka L + lemma o vkládání
- zařaď jazyk [latex]L = \{0^n1^n0^n\}[/latex] 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 [latex]L = \{ww| w \in \{0,1\}^*\}[/latex] 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 [latex]L1 = \{ww| w \in \{0,1\}^*\}[/latex] a [latex]L2 = \{wXw|w \in {0,1}^*\}[/latex], 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á)