Vomlelová - 4.6.2019

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).
Uživatelský avatar
LadyMalande
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 27. 1. 2019 21:14
Typ studia: Informatika Bc.

Vomlelová - 4.6.2019

Příspěvek od LadyMalande »

Ahoj, přidávám přibližné zadání písemky, přesná zadání už si nepamatuji, ale snad to pomůže ohledně toho, na co se podívat podrobněji.

Byly tam 3 jazyky na zařazení (z nich jeden trochu zákeřnější).
Měly se vybrat ekvivalentní stavy.
Byl zadán jazyk w2wR. Měli jsme si vybrat buď FA, PDA nebo TM a měli jsme k tomuto jazyku napsat automat.
Otázka na uzávěrové vlastnosti.
Jedna otázka na určení gramatiky - POZOR!! Kdo se učil ze slidů, které byli na webu od začátku semestru, nejspíš měl určení špatně (jako já), protože ve slidech nebyla popsána MONOTÓNNÍ gramatika. Po testu jsem o tom Vomlelové řekla a už by na webu měly být aktualizované slidy i s definicí monotónních gramatik. Mluvila o nich na začátku předposlední přednášky (na které jsem zrovna jako jediné nebyla :P).
Otázka, která tvrzení jsou pravdivá: Tvrzení o pumping lemmatu (nevím už kterém), Tvrzení o tom, pro jaké jazyky umíme vytvořit jaké automaty, gramatiky, nebo naopak - udělejte si v tom pořádek a není těžké odpověděť.
Při určování jazyků a existenci automatů pro jazyky tam bylo několikrát zmíněno DPDA a PDA, takže je dobré si ujasnit, který umí co, případně jak je rozlišit.
A bylo tam definujte PDA a u toho hlavně kontrolovala, jestli jsme napsali konečnost množiny, do které se zobrazuje přechodová funkce. Ve slidech vyznačeno jako FIN: -> P(FIN (Q ×Γ*)), To tam hodně lidem chybělo, tak si na to dejte pozor.

U ústní jsem si vytáhla rozdíl mezi wwR a w2WR. Zařadit je do Chomského hierarchie a udělat pro ně automaty.

Vomlelová byla i v 16:45 neskutečně trpělivá a milá, což beru jako jeden z posledních studentů toho dne na ústní velmi pozitivně. (Ten den nás bylo na termínu 39). Když jsem hned nedokázala modifikovat DPDA na PDA nebo naopak, tak mě nechala, ať si nad tím popřemýšlím. Pak se vrátila, řekla, že to šlo ještě jednodušeji, ale že to mám dobře a dala mi za 1.
U ústní se ještě ptala, jakou jsem měla písemku, jestli jsme probrali všechny chyby na ní a znovu ji prolétla očima - tak nevím, jestli do známky započítává i výsledky testu nebo si jen chtěla vyřadit písemku studenta, co odcházel od ústní.

Za mě byla písemka pohodová, měla jsem špatně asi 2-3 příklady, z nichž jeden byl kvůli neznalosti definice monotónní gramatiky. Pokud si v těch vztazích mezi automaty uděláte pořádek, tvrzení by snad měla být rozumně odvoditelná. Na druhou stranu vím, že přede mnou stál u opravování někdo, kdo odešel s nepořízenou se 4 body. Takže důležité je to nepodcenit, naučit se teorii, zvládnout obvyklé algoritmy a zařazování jazyků. Přeji všem hodně štěstí!
We now have a dog and Alistair is still the dumbest one in the party. - Morrigan
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“