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

===== Příklad 1 =====
**Navrhněte algoritmus, který pro daný netereminál //A// a bezkontextovou gramatiku //G// = (//N//, //Σ//, //P//, //S//) rozhodne, zda //A// je prvním symbolem nějaké větné formy //G//, t.j., zda //S// ⇒* //Aγ//, kde //γ// ∈ (//Σ// ∪ //N//)*. Uvědomte si, že některé neterminály mohou být přepsány na //ε//.**

Vstup: //G// = (//N//, //Σ//, //P//, //S//); //A// ∈ //N//\\
Výstup: Boolean (✔✘)
  - //A// = //S//: ✔
  - Sestrojíme množinu //E//, která bude obsahovat neterminály, které se přímo přepisují na //ε//.
  - Hledáme v //P// pravidla tvaru //X// → //E//* a všechna taková //X// přidáme do //E//. Opakujeme, dokud se //E// mění.
  - Hledáme v //P// pravidla tvaru //X// → //E//*//A//(//N// ∪ //Σ//)* a ze všch takových //X// uděláme množinu //T//. Tanto krok opakujeme, ale místo //A// dosazujeme neterminály z //T//, a stále rozšiřujeme množinu //T//, dokud můžeme.
  - Množina //T// obsahuje počáteční symbol //S//. ✔
  - ✘
===== Příklad 2 =====
**Nalezněte bezkontextovou gramatiku //G// s co nejméně pravidly takovou, že pokud v algoritmu 4.3 z přednášky pro odstranění zbytečných symbolů nejdříve provedeme body 3 a 4 (algoritmus 4.2 aplikujeme přímo na //G// a odstraníme nedostupné symboly) a na výslednou gramatiku aplikujeme body 1 a 2 (odstraníme neterminály jež negenerují žádné věty), dostaneme gramatiku obsahující nedostupný symbol.**

//G// = ({//A//, //B//, //C//}, {//a//, //b//, //c//}, //P//, //A//)
  * //A// → //BC// | //a//
  * //B// → //b//
  * //C// → //cC//
===== Příklad 3 =====
**Gramatiku //G// = ({//A//, //B//, //C//}, (//a//, //b//, //c//}, //P//, //A//) s pravidly**
  * **//A// → //Ba// | //a//**
  * **//B// → //BbC// | //C//**
  * **//C// → //Cc// | //A//**
**převeďte algoritmicky do Greibachové normální formy a Chomského normální formy.**

==== Greibachové normální forma ====
  - Ostranění //ε//-pravidel: žádné nejsou.
  - Odstranění levé rekurze:
    * //A// → //a// | //aA′//
    * //A′// → //a// | //C′a// | //B′a// | //C′B′a// | //aA′// | //C′aA′// | //B′aA′// | //C′B′aA′//
    * //B// → //C// | //CB′//
    * //B′// → //bC// | //bCB′//
    * //C// → //A// | //AC′//
    * //C′// → //c// | //cC′//
  - Relace uspořádání: //A′// < //C′// < //B′// < //B// < //C// < //A//
  - Dosazení v pořadí inverzním k relaci uspořádání:
    * //A// → //a// | //aA′//
    * //C// → //a// | //aA′// | //aC′// | //aA′C′//
    * //B// → //a// | //aA′// | //aC′// | //aA′C′// | //aB′// | //aA′B′// | //aC′B′// | //aA′C′B′//
    * //B′// → //bC// | //bCB′//
    * //C′// → //c// | //cC′//
    * //A′// → //a// | //ca// | //cC′a// | //bCa// | //bCB′a// | //cB′a// | //cC′B′a// | //aA′// | //caA′// | //cC′aA′// | //bCaA′// | //bCB′aA′// | //cB′aA′// | //cC′B′aA′//
  - Upravíme pravidla do greibachové normální formy:
    * //A// → //a// | //aA′//
    * //C// → //a// | //aA′// | //aC′// | //aA′C′//
    * //B// → //a// | //aA′// | //aC′// | //aA′C′// | //aB′// | //aA′B′// | //aC′B′// | //aA′C′B′//
    * //B′// → //bC// | //bCB′//
    * //C′// → //c// | //cC′//
    * //A′// → //a// | //cA″// | //cC′A″// | //bCA″// | //bCB′A″// | //cB′A″// | //cC′B′A″// | //aA′// | //cA″A′// | //cC′A″A′// | //bCA″A′// | //bCB′A″A′// | //cB′A″A′// | //cC′B′A″A′//
    * //A″// → //a//
==== Chomského normální forma ====
  - Vlastní gramatika: zadaná gramatika už vlastní je.
  - Bez jednoduchých pravidel:
    * //N<sub>A</sub>// = {//A//}
    * //N<sub>B</sub>// = {//A//, //B//, //C//}
    * //N<sub>C</sub>// = {//A//, //C//}
    * //A// → //Ba// | //a//
    * //B// → //BbC// | //Cc// | //Ba// | //a//
    * //C// → //Cc// | //Ba// | //a//
  - Chomského normální forma
    * //A// → //Ba′// | //a//
    * //B// → //B<bc>// | //Cc′// | //Ba′// | //a//
    * //C// → //Cc′// | //Ba′// | //a//
    * //a′// →  //a//
    * //c′// →  //c//
    * //<bc>// → //b′C//
    * //b′// →  //b//
===== Příklad 4 =====
**Navrhněte deterministický zásobníkový automat přijímající jazyk //L// z příkladu 6. Přechodovou funkci znázorněte //graficky//. Automat může mít maximálně 4 zásobníkové symboly a 4 stavy. Demonstrujte přijetí slova //abba//.**

//M// = ({//I//, //II//, //III//}, {//a//, //b//}, {//A//, //B//, //#//}, //δ//, //I//, //#//, {})

{{ pda.png }}
^  Čtený symbol  ^  Zásobník((Po provedení přechodu))  ^  Přechodová funkce  ^
| |//#//| |
|  //a//  |//#A//|{{a_bba.png}}|
|  //b//  |//#//|{{a_b_ba.png}}|
|  //b//  |//#B//|{{ab_b_a.png}}|
|  //a//  |//#//|{{abb_a_.png}}|
===== Příklad 5 =====
**Operátor paralelní kompozice (tzv. //shuffle//) || : Σ* × Σ* → 2<sup>Σ*</sup> je definován induktivně tak, že //w// || //ε// = //ε// || //w// = {//w//} a //aw//<sub>1</sub> || //bw//<sub>2</sub> = {//a//} · (//w//<sub>1</sub> || //bw//<sub>2</sub>) ∪ {//b//} · (a//w//<sub>1</sub> || //w//<sub>2</sub>). Dále, pro jazyky //L//<sub>1</sub> a //L//<sub>2</sub>, //L//<sub>1</sub> || //L//<sub>2</sub> = ∪<sub>//w//1 ∈ //L//1, //w//2 ∈ //L//2</sub>. Například {//aa//}||{//bb//} = {//aabb//, //abab//, //abba//, //baab//, //baba//, //bbaa//}. Dokažte, že množina bezkontextových jazyků není uzavřena na ||. Postupujte podobně, jako v důkazu neuzavřenosti vůči průniku, t.j., zvolte si dva bezkontextové jazyky //L//<sub>1</sub>, //L//<sub>2</sub> a dokažte pomocí pumping lemmatu, že //L//<sub>1</sub> || //L//<sub>2</sub> není bezkontextový.**

  * //L<sub>1</sub>// = {//a<sup>n</sup>b<sup>n</sup>// | //n// ≥ 0}
  * //L<sub>2</sub>// = {//0<sup>m</sup>1<sup>m</sup>// | //m// ≥ 0}
  * //L// = //L<sub>1</sub>// || //L<sub>2</sub>// = {//w// | #<sub>//a//</sub> = #<sub>//b//</sub> ∧ #<sub>//0//</sub> = #<sub>//1//</sub>}

Předpokládejme, že L je bezkontextový jazyk.

  * ∀ //k//: //z// ∈ //L// ∧ |//z//| ≥ //k//
  * //z// = //a<sup>k</sup>0<sup>k</sup>b<sup>k</sup>1<sup>k</sup>//, |//z//| = 4//k// ≥ //k//
  * ∀ //uvwxy//, //vx// ≠ //ε//, |//vwx//| ≤ //k//
  * //i// = 2

Takto mohou vzniknout řetězce ve tvaru //aa…aa00…00bb…bb11…11//. Počet opakování jednotlivých symbolů bude //k//, a pak pro libovolný výběr //vwx// takový, že |//vwx//| ≤ //k// a "napumpování" dojde vždy k narušení stejného počtu symbolů.

Z výše uvedeného tvrzení plyne, že jazyk L není bezkontextový, a tudíž __množina bezkontextových jazyků není uavřena na ||__.

===== Příklad 6 =====
**Nechť //L// je jazyk všech slov nad abecedou {//a//, //b//} se stejným počtem výskytů symbolu //a// jako výskytů symbolu //b//. Mějme gramatiku //G// = (//S//, {//a//, //b//}, //P//, //S//) s pravidly**
  * **//S// → //aSbS// | //bSaS// | //ε//**

==== Je gramatika jednoznačná? Dokažte. ====
__Není.__ Řetězec //abab// lze vygenerovat dvěma stromy.

{{  dertree1.png  }}

{{  dertree2.png  }}
==== Dokažte indukcí k délce slova, že L(G) ⊆ L. ====
  - ∀ //w// ∈ //L//(//G//): |//w//| = 0 → //w// ∈ //L//
  - //i// = 2\\ Z jazyka //L// můžeme udělat pouze tyto řetězce délky //i//: //ab//, //ba//. Zcela stejn řetězce můžeme vygenerovat i z jazyka //L//(//G//) a také to budou jediné možné řetězce o délce //i//, protože gramatika //G// vždy generuje stejný počet symbolů //a// jako //b//.
  - Výše uvedené tvrzení platí i pro všechna následující //i// + 2. (Vygenerované řetězce budou samozřejmě odpovídat patřičné délce //i//.)
==== Nechť pro i ∈ ℕ, Li = {w ∈ L | |w| ≤ i}. Dokažte indukcí k i, že Li ⊆ L(G) pro všechna i ∈ ℕ (a tedy L ⊆ L(G)). ====
**Nápověda:**
  - **Nejprve zdůvodněte následující tvrzení: Nechť slovo //w// ∈ //L// \ {//ε//} má tu vlastnost, že žádný jeho vlastní prefix vyjma //ε// nepatří do //L//. Potom //w// je tvaru //aub//, nebo //bua//, kde //u// ∈ //L//.**
  - **Pomocí tvrzení z bodu 1. ukažte, že každé slovo //w// ∈ //L// \ {//ε//} lze napsat ve tvaru //aubv//, nebo //buav//, kde //u//, //v// ∈ //L//.**
  - **Tvrzení z bodu 2. použijte v indukčním kroce.**

FIXME