IB102 — úkol 9, příklad 2 — řešení
Odevzdání: 26.11. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Mějme následující jazyk:
L = {cnbmam+ncmbn \n,me N}
Rozhodněte, zda jazyk L je či není bezkontextový a dokažte:
• Pokud L je bezkontextový, uveďte bezkontextovou gramatiku generující anebo zásobníkový automat akceptující daný jazyk. Gramatiku/automat zapište se všemi formálními náležitostmi.
• Pokud L není bezkontextový, dokažte tuto skutečnost pomocí Lemmatu o vkládání (tzv. Pumping Lemma).
Ř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 = cnbna2ncnbn. 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 c. Potom zřejmě ani v ani x neobsahují buď žádné a, anebo b . Zvolíme i = 2, pak zřejmě platí jedna z následujících možností: buď počet c v první části slova (tj. před částí se znaky a) je větší nez počet b v druhé části slova, anebo c v druhé části slova je větší než počet b v první části slova (a zároveň je porušena rovnost součtu b a c, který má být roven počtu a).
• Část v nebo x obsahuje alespoň jedno b. Potom zřejmě ani v ani x neobsahují buď žádné a, anebo c . Zvolíme i = 2, pak zřejmě platí jedna z následujících možností: buď počet b v první části slova (tj. před částí se znaky a) je větší nez počet c v druhé části slova, anebo b v druhé části slova je větší než počet c v první části slova (a zároveň je porušena rovnost součtu b a c, který má být roven počtu a).
• Část v nebo x obsahuje alespoň jedno a. Potom zřejmě ani v ani x neobsahují buď žádné b, anebo c . Zvolíme i = 2, pak zřejmě platí, že součet b a c v první, resp. druhé části slova je menší, než počet a (který má být jejich součtu roven).
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 uvlwxly ^ L. Podle lemmatu o vkládání pro bezkontextové jazyky tedy L není bezkontextový.