Formální jazyky a automaty – pokyny k samostudiu, domácí úkoly a online cvičení

Týden 11: uzávěrové vlastnosti bezkontextových jazyků, deterministické zásobníkové automaty (DPDA), Turingovy stroje (TM)

Samostudium

Nastudujte si prosím ze skript podkapitoly 3.3 až 4.3 včetně, tedy strany 92-120.

skripta k IB005
verze z února 2014 s některými opravenými překlepy

K dispozici jsou záznamy loňských přednáškek IB005 ze 3.4.2019 (vlastnosti bezkontextových jazyků a definice DPDA), ze 4.4.2019 (poznámky o deterministických syntaktických analýzách, vlastnosti deterministických bezkontextových jazyků, motivace pro definici TM) a z 10.4.2019 (definice TM, metody konstrukce TM, modifikace TM):

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/vi_js2019/89814529/
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/vi_js2019/89835923/
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/vi_js2019/89977934/

Látka je také částečně pokryta na přednáškách IB102 z 9.12.2019 (vlastnosti bezkontextových jazyků; v úvodu přednášky je prezentován algoritmus Cocke-Younger-Kasami, který se v IB005 neučí) a z 16.12.2019 (deterministické bezkontextové jazyky, Turingovy stroje):

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/zaznamy_prednasek_ib102_-_podzim_2019/95950564/

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/zaznamy_prednasek_ib102_-_podzim_2019/96156773/

Cvičení

Cvičení proběhlo formou telekonference ve čtvrtek 30.4.2020 od 14:00, k dispozici je záznam:

11. cvičení

Tabuli popsanou během cvičení si můžete

Domácí úkoly

Dva domácí úkoly, až 0,5 tvrdého a 0,5 měkkého bodu dohromady.

úkol 11, příklad 1 ‒ LaTeX
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 8. 5. 2020 12:00 fyzicky do schránky před D1 nebo elektronicky ve formátu .pdf do příslušné odevzdávárny. Papír nesmí být přeložený či jinak poškozený a musí být vyplněná hlavička, i elektronicky odevzdané verze se budou tisknout a následně skenovat. Pro tvorbu řešení můžete přímo upravit .tex se zadáním (k nalezení v této složce) + potřebujete styl fja.cls rovněž zde, můžete použít přiložený návod na sazbu.
úkol 11, příklad 2 ‒ LaTeX
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 8. 5. 2020 12:00 fyzicky do schránky před D1 nebo elektronicky ve formátu .pdf do příslušné odevzdávárny. Papír nesmí být přeložený či jinak poškozený a musí být vyplněná hlavička, i elektronicky odevzdané verze se budou tisknout a následně skenovat. Pro tvorbu řešení můžete přímo upravit .tex se zadáním (k nalezení v této složce) + potřebujete styl fja.cls rovněž zde, můžete použít přiložený návod na sazbu.
úkol 11, příklad 1
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 8. 5. 2020 12:00 fyzicky do schránky před D1 nebo elektronicky ve formátu .pdf do příslušné odevzdávárny. Papír nesmí být přeložený či jinak poškozený a musí být vyplněná hlavička, i elektronicky odevzdané verze se budou tisknout a následně skenovat. Pro tvorbu řešení můžete přímo upravit .tex se zadáním (k nalezení v této složce) + potřebujete styl fja.cls rovněž zde, můžete použít přiložený návod na sazbu.
úkol 11, příklad 2
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 8. 5. 2020 12:00 fyzicky do schránky před D1 nebo elektronicky ve formátu .pdf do příslušné odevzdávárny. Papír nesmí být přeložený či jinak poškozený a musí být vyplněná hlavička, i elektronicky odevzdané verze se budou tisknout a následně skenovat. Pro tvorbu řešení můžete přímo upravit .tex se zadáním (k nalezení v této složce) + potřebujete styl fja.cls rovněž zde, můžete použít přiložený návod na sazbu.

Odevzdávárny

Odevzdávárna DÚ: úkol 11, příklad 1
Prosím odevzdávejte jen úkol 11, příklad 1. Odevzdávejte ve formátech a kvalitě specifikované v interaktivní osnově, odevzdání musí být podepsané (tedy se jménem uvnitř dokumentu).
Odevzdávárna DÚ: úkol 11, příklad 2
Prosím odevzdávejte jen úkol 11, příklad 2. Odevzdávejte ve formátech a kvalitě specifikované v interaktivní osnově, odevzdání musí být podepsané (tedy se jménem uvnitř dokumentu).

Řešení

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/du/reseni/reseni1102.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/du/reseni/reseni1101.pdf

Předchozí
Následující