Vomlelová 29.5.2018

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).
Speedding
Matfyz(ák|ačka) level I
Příspěvky: 35
Registrován: 10. 1. 2017 19:32
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Vomlelová 29.5.2018

Příspěvek od Speedding »

Na ústní měla připravené papírky s tématy. Bylo tam například pumping lemma pro reg. jazyky i s důkazem, uzávěrové vlastnosti deterministických bezkontextových jazyků, ale objevilo se tam i hardcore téma typu diagonální jazyk. Je důležité se na tu ústní naučit, protože když nebudete téměř nic vědět, může vás vyhodit, i když budete mít z písemky plný počet bodů. Pokud ale máte dobrou ústní, zdálo se mi, že i se sedmi body z písemky můžete dostat jedničku. Pokud si u někoho není jistá známkou, říkala, že všem takovým dává rozhodující příklad, aby zařadili do Chomského hierarchie jazyk \{0^i 1^i 0^i : i \in \mathbb{N}\}. Na jiném termínu to třeba bude zase nějaký jiný jazyk, každopádně je asi fajn se naučit používat lemma pro bezkontextové jazyky.

Písemka se od té na moodlu lišila v podstatě jenom tím, že tam byli tři příklady na zařazení jazyků. Všechny tři jazyky si byly (na první pohled) dost podobné... Jinak je asi pravidlem, že do každé písemky dá minimálně dva příklady na zařazení jazyků, jeden příklad na CYK, jeden příklad na ekvivalenci stavů a něco na uzávěrové vlastnosti.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“