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

Týden 9: transformace bezkontextových gramatik, Chomského normální forma (CNF), Greibachové normalní forma (GNF)

Samostudium

Nastudujte si prosím strany 64 (začněte za Přikladem 3.12) až 76 (po začátek části 3.2) ze skript. Lemma o vkládání pro bezkontextové jazyky (Věta 3.24) bude na cvičeních až v 10. 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 ze 14.3.2019 (odstranění ε-pravidel a jednoduchých pravidel, CNF) a z 20.3.2019 (lemma o vkládání pro bezkontextové jazyky, GNF):

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

Stejná témata byla prezentována i na přednáškách IB102 z 11.11.2019 (odstranění ε-pravidel a jednoduchých pravidel, CNF, lemma o vkládání pro bezkontextové jazyky) a z 18.11.2019 (GNF):

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/95155810/
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/

Cvičení

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

9. cvičení

Tabuli popsanou během cvičení si můžete prohlédnout zde.

Domácí úkoly

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

úkol 09, příklad 1 ‒ LaTeX
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 24. 4. 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 09, příklad 2 ‒ LaTeX
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 24. 4. 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 09, příklad 1
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 24. 4. 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 09, příklad 2
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 24. 4. 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 09, příklad 1
Prosím odevzdávejte jen úkol 09, 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 09, příklad 2
Prosím odevzdávejte jen úkol 09, 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/reseni0901.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2020/IB005/um/du/reseni/reseni0902.pdf

Předchozí
Následující