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(uv2wx2y) > 2j^\)(uv2wx2y\ a tedy uv2wx2y ^ 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(uv2wx2y) > j^c(uv2wx2y\ a tedy uv2wx2y ^ 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ý.
IB102 - úkol 9 - řešení
Odevzdání: 5.12. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Mějme gramatiku G = ({S, A, B, C, D}, {a, b}, P, S), kde
P = {   S  ->  Aa\ BaC, A  ->  Sa | AD, B  -+ Sb\b, C  ->  CCa | b, D  ->  aD\bD }.
Převeďte tuto gramatiku do Greibachové normálni formy použitím algoritmů z přednášky.
Poznámka: Nezapomeňte si nejdřív zkontrolovat, zdaje pro použití algoritmů gramatika ve vhodném vstupním tvaru.
Řešení: Pro provedení převodu na GNF potřebujeme, aby byla gramatika bez levé rekurze a vlastní. Algoritmus pro odstranění levé rekurze rovněž vyžaduje na vstupu vlastní gramatiku. Zadaná gramatika není vlastní, protože není redukovaná, obsahuje totiž nenormovaný neterminál. Provedeme tedy nejprve odstranění zbytečných neterminálů. Zřejmě jediný nenormovaný neterminál je D a po jeho odstranění jsou všechny neterminály normované a dosažitelné. Máme tedy G' = ({S, A, B, C}, {a, b}, P', S), kde
P' = {   S  ->  Aa\ BaC, A Sa, B  -+ Sb\b, C  ->  CCa\b }.
Tato grmatika už je vlastní, můžeme tedy provést algoritmus pro odstranění levé rekurze. Nejprve si zvolíme uspořádání na neterminálech, například S < A < B < C. Dále provádíme substituci podle algoritmu. Pravidla S se nemění:
S -> Aa | BaC
V pravidlech pro A nejprve substituujeme za počáteční S:
A —> Aaa | BaCa
Následně odstraníme bezprostřední levou rekurzi:
A ->• BaCa | BaCaÄ A1 —> aa | aaA'
V pravidlech pro B nejprve substituujeme za počáteční S:
B     Aab I BaCb I b
Následně substituujeme za počáteční A:
B —> BaCaab \ BaCaA'ab \ BaCb \ b A nakonec odstraníme bezprostřední levou rekurzi: B -> b I bB'
B' —y aCaab | aCaA'ab \ aCb \ aCaabB' \ aCaA'abB' \ aCbB'
V pravidlech pro C pouze odstraníme bezprostřední levou rekurzi:
C -> b I bC C ^Ca\ CaC'
Výsledná gramatika bez levé rekurze je G" = ({S, A, A', B, B', C, C'}, {a, b}, P", S), kde
P" = {    S  -+  Aa | BaC,
A  ->•  BaCa \ BaCaÄ, A' —>   aa | aaA', B  ->  6 | bB',
B' —>   aCaab \ aCaA'ab \ aCb \ aCaabB' \ aCaA'abB' | aCbB',
C  -+  b\ bC',
C'  -+  Ca\ CaC' }.
Tato gramatika je zřejmě i vlastní, můžeme tedy rovnou pokračovat algoritmem pro převod na GNF. Lineární uspořádání splňující podmínku v algoritmu je například C' < B' < A' < S < A < B < C. Provedeme tedy substituci podle algoritmu a nahradíme terminály na nepočátečních pozicích neterminály. Dostaneme tak výslednou gramatiku:
G'" = ({S, A, A', B, B', C, C', a', b'}, {a, b}, P'", S), kde
P'" = {   C b\ bC',
B -> 6 j bB',
A -+ ba'C a' \ bB'a'Ca! \ ba! C a! N \ bB'a'Ca'A',
S ba'Ca'a' \ bB'a'Ca!a! \ ba'Ca'A'a' \ bB'a'Ca'A'a' \ ba!C \ bB'a'C,
A' —> aa' | aa'A',
B' aCa'a'b' | aCa'A'a'b' \ aCb' \ aCa'a'bxB' | aCa'A'a'bxB' \ aCb'B',
C -+ ba' | bC'a' I ba'C \ bC'a'C }.