Zkouška Surynek první termín v červnu 2016

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
Quique
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 10. 2. 2016 15:28
Typ studia: Informatika Bc.

Zkouška Surynek první termín v červnu 2016

Příspěvek od Quique »

Jako obvykle u Surynka.. zařadit jazyk do Chomského hierarchie a potom jedna teoretická otázka

otázky, které jsem zaslechl u ostatních:
Nedeterministické KA a jejich síla;
lineárně omezené TS a proč kont. jazyk;
korespondenční poroblém;
gramatiky TS a vztah k rekurzivně spočetným jazykům;
regulární výrazy - co to je a k čemu to je;
algoritmus CYK;
Myhill-Nerod;
Vícepáskové deterministické TS;
jazyk Lu a halting problem;
Bezkontextové pumping lemma;
nedeterministické TS a převod na deterministické;
vztah kontextových a nezkracujících gramatik

ale vybírá náhodně z velmi dlouhého seznamu, na kterém je zcela vše, co bylo na přednášce


ještě v příloze přidávám mojí přípravu na zařazení jazyků (jazyky jsem bral z fora a různých cvik)

plus ještě jeden hnusný jazyk, který se na zkoušce vyskytl:
a^(i^2 + i + 1)

a ještě tam bylo mnoho takových, kde se vyskytuje: kod(T)...
Přílohy
reseni jazyku.txt
(302 bajtů) Staženo 231 x
2016-06-01 12.52.48.jpg
2016-06-01 12.52.33.jpg
befelemepeseveze

Re: Zkouška Surynek první termín v červnu 2016

Příspěvek od befelemepeseveze »

Jazyk č. 4 se u zkoušky objevuje i ve variantě s rovností u = v. V takovém případě je kontextový.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“