Matfyz Wiki
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)...
Attachments: