IB102 - úkol 9 - řešení
Odevzdání: 5.12. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Mějme následující jazyk:
L = {we {a, b, c, d}* | #aH = 2#b(w) a #a(w) < #c(w)}
Rozhodněte, zdaje tento jazyk bezkontextový, a své rozhodnutí dokažte. (Pro důkaz toho, že je jazyk bezkontextový, stačí sestrojit příslušnou bezkontextovou gramatiku nebo zásobníkový automat.)
Řešení: Jazyk L není bezkontextový. Dokážeme to pomocí lemmatu o vkládání (Pumping Lemma) pro bezkontextové jazyky.
Nechť n je libovolné přirozené číslo. Zvolíme slovo z = a2nbnc2n+1. Zřejmě platí z E L a \z\ > n. Nyní prozkoumáme všechna rozdělení z = uvwxy taková, že \vwx\ < n a vx ^ e. Každé takové rozdělení je jednoho z těchto druhů:
• Část v nebo x obsahuje alespoň jedno a. Potom zřejmě ani v ani x neobsahují žádné c. Zvolíme i = 2, pak zřejmě platí #a(uv2wx2y) > #c(uv2wx2y), a tedy uv2wx2y ^ L. (Pumpováním se zvětší počet a, ale počet c se nezmění.)
• Části v ani x neobsahují žádné a, ale alespoň jedna z nich obsahuje alespoň jedno b. Zvolíme i = 0, pak zřejmě platí #a(uv°wx°y) > 2#b(uv°wx°y), a tedy uv°wx°y ^ L. (Pumpováním se zmenší počet b, ale počet a se nezmění.)
• Části v ani x neobsahují žádná a ani žádná b, musí tedy obsahovat pouze symboly c. Zvolíme i = 0, pak zřejmě platí #a(uv°wx°y) > #c(uv°wx°y), a tedy uv°wx°y ^ L. (Pumpováním se zmenší počet c, ale počet a se nezmění.)
Je jasné, že tyto tři body pokrývají všechny možnosti, které mohou nastat. Ukázali jsme tedy, že pro každé rozdělení z = uvwxy je možno najít i takové, že uv%wx%y ^ L. Podle lemmatu o vkládání pro bezkontextové jazyky tedy L není bezkontextový.