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

Týden 10: Lemma o vkládání pro bezkontextové jazyky, zásobníkové automaty (PDA), nedeterministická syntaktická analýza

Samostudium

Nastudujte si prosím ze skript podkapitolu 3.2, tedy strany 76-92. Na cvičeních v tomto týdnu bude též Lemma o vkládání pro bezkontextové jazyky (Věta 3.24 a text na stranách 68-71), které bylo v rámci samostudia uvedeno již v 9. týdnu.

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 z 20.3.2019 (část o zásobníkových automatech začíná kolem 1:21:40, na začátku přednášky se probírá Lemma o vkládání pro bezkontextové jazyky, které možná stojí za zopakování) a z 21.3.2019 (záznam z neznámých důvodů neobsahuje úvodní pasáž přednášky) a z 27.3.2019 (oba posledně jmenované záznamy doporučujeme zhlédnout celé):
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/vi_js2019/89419666/
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/vi_js2019/89450732/
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/vi_js2019/89604991/
Látka je také částečně pokryta na přednáškách IB102 z 18.11.2019 (definice zásobníkových automatů), z 25.11.2019 (metody akceptování, rozšířené zásobníkové automaty) a z 2.12.2019 (zásobníkové automaty a bezkontextové gramatiky, nedeterministická syntaktická analýza):
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/95343238/
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/95529213/
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/95755257/

Cvičení

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

10. 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 10, příklad 1 ‒ LaTeX
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 1. 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 10, příklad 2 ‒ LaTeX
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 1. 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 10, příklad 1
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 1. 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 10, příklad 2
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 1. 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 10, příklad 1
Prosím odevzdávejte jen úkol 10, 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 10, příklad 2
Prosím odevzdávejte jen úkol 10, 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).

Řešení

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

Předchozí
Následující