Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- tin:ukoly:2011:2 [10. 11. 2011, 14.49:12] – [Příklad 3] mensi pitel
+++ tin:ukoly:2011:2 [18. 08. 2026, 18.00:40] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== Úkol 2 ======
-Bc. Jan Kaláb %%<[email protected]>%%
-===== Příklad 1 =====
-**Uvažte jazyk //L//₁ = {//wcⁱ// | //w// ∈ {//a//, //b//}* ∧ (#<sub>//a//</sub>(//w//) = //i// ∨ #<sub>//b//</sub>(//w//) = //i//)}**.
-**Sestavte gramatiku //G//₁ takovou, že //L//(//G//₁) = //L//₁.**
-//G//₁ = ({//S//, //A//, //B//}, {//a//, //b//, //c//}, //P//, //S//)
-//P//:
-  * //S// → //A// | //B// | //ε//
-  * //A// → //aAc// | //bA// | //ε//
-  * //B// → //bBc// | //aB// | //ε//
-**Algoritmickým postupem převeďte gramatiku //G//₁ na zásobníkový automat provádějící syntaktickou analýzu zdola nahoru.**
-//M// = ({//q//, //r//}, {//a//, //b//, //c//}, {//S//, //A//, //B//, //a//, //b//, //c//, //#//}, //δ//, //q//, //#//, {//r//})
-Reduce:
-  * //δ//(//q//, //ε//, //A//) = {(//q//, //S//)}
-  * //δ//(//q//, //ε//, //B//) = {(//q//, //S//)}
-  * //δ//(//q//, //ε//, //bA//) = {(//q//, //A//)}
-  * //δ//(//q//, //ε//, //aAc//) = {(//q//, //A//)}
-  * //δ//(//q//, //ε//, //aB//) = {(//q//, //B//)}
-  * //δ//(//q//, //ε//, //bBc//) = {(//q//, //B//)}
-  * //δ//(//q//, //ε//, //ε//) = {(//q//, //A//), (//q//, //B//)}
-Shift:
-  * //δ//(//q//, //a//, //ε//) = {(//q//, //a//)}
-  * //δ//(//q//, //b//, //ε//) = {(//q//, //b//)}
-  * //δ//(//q//, //c//, //ε//) = {(//q//, //c//)}
-Accept:
-  * //δ//(//q//, //ε//, //S#//) = {(//r//, //ε//)}
-**Lze jazyk //L//₁ přijmout deterministickým zásobníkovým automatem (DZA)? Zdůvodněte své tvrzení (formální důkaz se nepožaduje).**
-Nelze. Kvůli ∨ v zadání nevíme, zda použít podmínku #<sub>//a//</sub>(//w//) nebo #<sub>//b//</sub>(//w//), a nevíme tedy, zda na zasobníku počítat //b// nebo //a//.
-===== Příklad 2 =====
-**Mějme jazyky //L//₁ = {//aⁱbʲcⁱdʲ// | //i//, //j// ∈ ℕ} a //L//₂ = {//aⁱbⁱcʲdʲ// | //i//, //j// ∈ ℕ}.((0 ∈ ℕ)) Pro každý z jazyků //L//₁ a //L//₂ dokažte, nebo vyvraťte, zda je bezkontextový.**
-==== L₁ ====
-Důkaz sporem.
-Předpokládejme, že jazyk //L//₁ je bezkontextový. Pak podle pumping lemmatu pro bezkontextové jazyky existuje konstanta //k// taková, že je-li //z// ∈ //L//₁ a |//z//| ≥ //k//, pak lze //z// napsat ve tvaru: //z// = //uvwxy//, //vx// ≠ //ε//, |//vwx//| ≤ //k// a pro všechna //i// ≥ 0 je //uvⁱwxⁱy// ∈ //L//<sub>1</sub>.
-Zvolíme si //z// = //uᵏvᵏwᵏxᵏyᵏ//, |//z//| > //k//, //i// > 1, pak může dojít k následujícímu rozdělení:
-  * //vwx// = //aᵐ//, //m// ≤ //k//, #<sub>//a//</sub>(//z//) ≠ #<sub>//c//</sub>(//z//)
-  * //vwx// = //aᵐbⁿ//, //m// + //n// ≤ //k//, #<sub>//a//</sub>(//z//) ≠ #<sub>//c//</sub>(//z//) ∨ #<sub>//b//</sub>(//z//) ≠ #<sub>//d//</sub>(//z//)
-  * //vwx// = //bᵐ//, //m// ≤ //k//, #<sub>//b//</sub>(//z//) ≠ #<sub>//d//</sub>(//z//)
-  * //vwx// = //bᵐcⁿ//, //m// + //n// ≤ //k//, #<sub>//a//</sub>(//z//) ≠ #<sub>//c//</sub>(//z//) ∨ #<sub>//b//</sub>(//z//) ≠ #<sub>//d//</sub>(//z//)
-  * //vwx// = //cᵐ//, //m// ≤ //k//, #<sub>//a//</sub>(//z//) ≠ #<sub>//c//</sub>(//z//)
-  * //vwx// = //cᵐdⁿ//, //m// + //n// ≤ //k//, #<sub>//a//</sub>(//z//) ≠ #<sub>//c//</sub>(//z//) ∨ #<sub>//b//</sub>(//z//) ≠ #<sub>//d//</sub>(//z//)
-  * //vwx// = //dᵐ//, //m// ≤ //k//, #<sub>//b//</sub>(//z//) ≠ #<sub>//d//</sub>(//z//)
-Ukázali jsme, že nelze najít takové rozdělení, které by splňovalo podmínky pumping lemmatu pro bezkontextový jazyk, což je spor, a jazyk tedy není bezkontextový.
-==== L₂ ====
-//G// = ({//A//, //S//, //T//}, {//a//, //b//, //c//, //d//}, //P//, //A//)
-  * //A// → //ST//
-  * //S// → //aSb// | //ε//
-  * //T// → //cTd// | //ε//
-K jazyku //L//₂ lze sestavit bezkontextovou gramatiku, tudíž je bezkontextový.
-===== Příklad 3 =====
-**Mějme jazyky //L//₃ ∈ ℒ₃ a //L//₂ ∈ ℒ₂. Dokažte, že problém //L//₂ ⊆<sup>?</sup> //L//₃ je (eventuelně není) rozhodnutelný? K důkazu použijte uzávěrové vlastnosti bezkontextový a regulárních jazyků.**
-Důkaz sporem.{{ rozhodnut.png?100|Ilustrace nerozudnotelnosti}}
-  * Předpokládejme, že platí definice podmožiny: //L//₂ ⊆ //L//₃ ⇔ //L//₂ ∩ //L//₃′ = ∅((′ zde značí doplněk)).
-  * Víme, že ℒ₃ jsou uzavřené vůči doplňku, čili //L//₃′ = ℒ₃ − //L//₃.
-  * Pokud ale bude //L//₂ čistě bezkontextový, bude pak platit //L//₂ ∩ //L//₃′ = ∅, a přitom není podmnožinou //L//₃ (viz ilustrace), což je spor!
-  * Problém //L//₂ ⊆<sup>?</sup> //L//₃ je tedy nerozhodnutelný.
-===== Příklad 4 =====
-**Uvažujte jazyk //L//₄, který je generován gramatikou\\ //G//₄ = ({//E//, //T//, //F//}, {//(//, //)//, //true//, //or//, //and//, //not//}, //P//, //E//), kde**
-**//P//:**
-  * **//E// → //E or T// | //T//**
-  * **//T// → //T and F// | //F//**
-  * **//F// → //(E)// | //not(E)// | //true//**
-**Sestrojte //deterministický// zásobníkový automat přijímající jazyk //L//₄ a demonstrujte jeho funkci na přijetí řetězce //(true or not(true)) and true//.**
-{{ pda.png |Deterministický zásobníkový automat přijímající jazyk L4}}((U přechodu ve trvaru //a//, //b// / //xyz// považuji //z// za nový vrchol zásobníku.))
-  - //δ//(//S//, //(//, //#//)
-  - //δ//(//S//, //true//, //]//)
-  - //δ//(//Z//, //or//, //]//)
-  - //δ//(//S//, //not//, //]//)
-  - //δ//(//N//, //(//, //(//)
-  - //δ//(//S//, //true//, //)//)
-  - //δ//(//Z//, //)//, //)//)
-  - //δ//(//Z//, //)//, //]//)
-  - //δ//(//F//, //and//, //#//)
-  - //δ//(//S//, //true//, //#//)
-===== Příklad 5 =====
-**Mějme gramatiku //G//₅ = ({//S//, //A//, //B//, //C//}, {//a//, //b//, //c//}, //P//, //S//), kde**
-**//P//:**
-  * **//S// → //aACa//**
-  * **//A// → //B// | //a//**
-  * **//B// → //C// | //c//**
-  * **//C// → //Cc// | //bC// | ε**
-**Převeďte gramatiku //G//₅ //algoritmicky// do Chomského normální formy.**
-Bez ε přechodů:
-  * //N<sub>ε</sub>//⁰ = ∅
-  * //N<sub>ε</sub>//¹ = {//C//}
-  * //N<sub>ε</sub>//² = {//C//, //B//}
-  * //N<sub>ε</sub>//³ = {//C//, //B//, //A//}
-  * //N<sub>ε</sub>//⁴ = {//C//, //B//, //A//} = //N<sub>ε</sub>//³ = //N<sub>ε</sub>//
-  * //S// → //aACa// | //aAa// | //aCa// | //aa//
-  * //A// → //B// | //a//
-  * //B// → //C// | //c//
-  * //C// → //Cc// | //b// | //bC// | //c//
-Bez jednoduchých pravidel:
-  * //N<sub>S</sub>//⁰ = {//S//}
-  * //N<sub>S</sub>//¹ = {//S//} = //N<sub>S</sub>//⁰ = //N<sub>S</sub>//
-  * //N<sub>A</sub>//⁰ = {//A//}
-  * //N<sub>A</sub>//¹ = {//A//, //B//}
-  * //N<sub>A</sub>//² = {//A//, //B//, //C//}
-  * //N<sub>A</sub>//³ = {//A//, //B//, //C//} = //N<sub>A</sub>//² = //N<sub>A</sub>//
-  * //N<sub>B</sub>//⁰ = {//B//}
-  * //N<sub>B</sub>//¹ = {//B//, //C//}
-  * //N<sub>B</sub>//² = {//B//, //C//} = //N<sub>B</sub>//¹ = //N<sub>B</sub>//
-  * //N<sub>C</sub>//⁰ = {//C//}
-  * //N<sub>C</sub>//¹ = {//C//} = //N<sub>C</sub>//⁰ = //N<sub>C</sub>//
-  * //S// → //aACa// | //aAa// | //aCa// | //aa//
-  * //A// → //Cc// | //a// | //b// | //bC// | //c//
-  * //B// → //Cc// | //b// | //bC// | //c//
-  * //C// → //Cc// | //b// | //bC// | //c//
-Vlastní gramatika (odstranění zbytečných a nedostupných symbolů):
-  * //V//₀ = {//S//}
-  * //V//₁ = {//S//, //a//, //A//, //C//}
-  * //V//₂ = {//S//, //a//, //A//, //C//, //c//, //b//}
-  * //V//₃ = {//S//, //a//, //A//, //C//, //c//, //b//} = //V//₂ = //V//
-  * //S// → //aACa// | //aAa// | //aCa// | //aa//
-  * //A// → //Cc// | //a// | //b// | //bC// | //c//
-  * //C// → //Cc// | //b// | //bC// | //c//
-Chomského normální forma:
-//G// = ({//S//, <//ACa//>, <//Aa//>, <//Ca//>, //A//, //C//, //a//′, //b//′, //c//′}, {//a//, //b//, //c//}, //P//, //S//)
-//P//:
-  * //S// → //a//′<//ACa//> | //a//′<//Aa//> | //a//′<//Ca//> | //a//′//a//′
-  * <//ACa//> → //A//<//Ca//>
-  * <//Aa//> → //Aa//′
-  * <//Ca//> → //Ca//′
-  * //A// → //Cc//' | //a// | //b// | //b//′//C// | //c//
-  * //C// → //Cc//' | //b// | //b//′//C// | //c//
-  * //a//′ → //a//
-  * //b//′ → //b//
-  * //c//′ → //c//
-**Převeďte gramatiku //G//₅ //algoritmicky// do Greibachové normální formy.**
-Vlastní gramatika:
-  * Viz převod do Chomského normální formy
-Odstranění levé rekurze (//S// < //A// < //C//):
-  * //S// → //aACa// | //aAa// | //aCa// | //aa//
-  * //A// → //Cc// | //a// | //b// | //bC// | //c//
-  * //C// → //b// | //bC// | //bC//′ | //bCC//′ | //c// | //cC//′
-  * //C//′ → //c// | //cC//′
-Greibachové normální forma:
-//G// = ({//S//, //A//, //C//, //C//′, //a//′, //c//′}, {//a//, //b//, //c//}, //P//, //S//)
-//P//:
-  * //S// → //aACa//′ | //aAa//′ | //aCa//′ | //aa//′
-  * //A// → //a// | //b// | //bC// | //bC//′//c//′ | //bCC//′//c//′ | //bCc//′ | //bc//′ | //c// | //cC//′//c//′ | //cc//′
-  * //C// → //b// | //bC// | //bC//′ | //bCC//′ | //c// | //cC//′
-  * //C//′ → //c// | //cC//′
-  * //a//′ → //a//
-  * //c//′ → //c//

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku