====== Ú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