====== Úkol 2 ======
Bc. Jan Kaláb %%<xkalab00@stud.fit.vutbr.cz>%%

===== 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//), (//q//, //S//)}

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ů.**
  * Platí definice podmnožiny: L₂ ⊆ L₃ ⇔ L₂ ∩ L₃′ = ∅((′ značí doplněk))
  * ℒ₃ jsou na doplněk uzavřené
  * ℒ₂ jsou uzavřené na průnik s ℒ₃
  * Problém se tedy redukoval na prázdnost ℒ₂, a ten je rozhodnutelný.
  * Problém //L//₂ ⊆<sup>?</sup> //L//₃ je tady také rozhodnutelný.
===== 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//