====== Ú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:
* //NA// = {//A//}
* //NB// = {//A//, //B//, //C//}
* //NC// = {//A//, //C//}
* //A// → //Ba// | //a//
* //B// → //BbC// | //Cc// | //Ba// | //a//
* //C// → //Cc// | //Ba// | //a//
- Chomského normální forma
* //A// → //Ba′// | //a//
* //B// → //B// | //Cc′// | //Ba′// | //a//
* //C// → //Cc′// | //Ba′// | //a//
* //a′// → //a//
* //c′// → //c//
* //// → //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Σ* je definován induktivně tak, že //w// || //ε// = //ε// || //w// = {//w//} a //aw//1 || //bw//2 = {//a//} · (//w//1 || //bw//2) ∪ {//b//} · (a//w//1 || //w//2). Dále, pro jazyky //L//1 a //L//2, //L//1 || //L//2 = ∪//w//1 ∈ //L//1, //w//2 ∈ //L//2. 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//1, //L//2 a dokažte pomocí pumping lemmatu, že //L//1 || //L//2 není bezkontextový.**
* //L1// = {//anbn// | //n// ≥ 0}
* //L2// = {//0m1m// | //m// ≥ 0}
* //L// = //L1// || //L2// = {//w// | #//a// = #//b// ∧ #//0// = #//1//}
Předpokládejme, že L je bezkontextový jazyk.
* ∀ //k//: //z// ∈ //L// ∧ |//z//| ≥ //k//
* //z// = //ak0kbk1k//, |//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