IB102 - úkol 10 - řešení
Odevzdání: 6.12. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [2 body] Mejme gramatiku G = ({S, X, Y, Z}, {a, b, c}, P, S), kde
P = {   S  — XZX,
X  — Xbc | Ybc, Y  —  aa | Saa, Z  —  ZZb | c }.
Ke gramatice G sestrojte (použitím algoritmu z prednašky) ekvivalentní gramatiku v Grei-bachove normainí forme.
Rešeni: Gramatika je zrejme redukovana, bez jednoduchých a e-pravidel. ZaCneme tedy rovnou odstranením leve rekurze. Zvolíme si napr. nýsledující usporadaní:
S <X <Y <Z
Dale postupujeme podle algoritmu z prednasky.
1. Neterminal S neobsahuje prímou levou rekurzi, jeho pravidla tedy ponechanie beze zmeny.
2. Neterminal X neobsahuje pravidla, jejichz prava strana by zaďnala S, ale obsahuje prímou levou rekurzi. Tu odstraníme:
X — Ybc | YbcX1 X' — bc | bcX'
3. Neterminal Y obsahuje pravidlo Y — Saa, to odstraníme a dostaneme:
Y — aa | XZXaa Daíle odstraníme pravidlo Y — XZXaa:
Y — aa | YbcZXaa | YbcX Z X aa Nakonec odstraníme prímou levou rekurzi: Y —> aa | aaY'
Y' — bcZXaa | bcX'ZXaa | bcZXaaY' | bcX'ZXaaY'
4. Neterminal Z obsahuje pouze prímou levou rekurzi, tu odstraníme:
Z — c | cZ'
Z'   Zb ZbZ'
Jako výsledek odstranění levé rekurze dostáváme gramatiku s těmito pravidly:
S	—
X	—
X'	—
Y	—
Y'	—
Z	-
Z'	->•
— XZX Ybc | YbcX' bc I bcX' aa I aaY'
— bcZXaa | bcX'ZXaa | bcZXaaY' | bcX'ZXaaY'
c | cZ' Zb | ZbZ'
Nyní můžeme přikročit k samotnému převodu na GNF. Uspořádání, požadované v algoritmu, je například toto:
Z' < Y' < X' < S < X < Y < Z
Dale pokračujeme v substitucích podle algoritmu (nasledující řádky jsou uspořádány podle toho, v jakem pořadí algoritmus žpracovíva jednotlive neterminaly).
c | cZ'
aa | aaY'
aabc | aaY'bc | aabcX' | aaY'bcX'
aabcZX | aaY'bcZX | aabcX'ZX | aaY'bcX'ZX bc | bcX'
bcZXaa | bcX'ZXaa | bcZXaaY' | bcX'ZXaaY' cb | cZ'b | cbZ' | cZ'bZ'
Z	—
Y	—
X	—
S	—
X'	—
Y'	—
Z'	->•
Nakonec nahradíme terminíly na jiných než počatečních pozicích příslusními neterminaly. Výslední gramatika je tedy G' = ({S,X,X',Y,Y',Z, Z', a',b',d}, {a,b,c}, P', S), kde
P = { S	—	aa'b'c'ZX | aa'Y'b'c'ZX | aa'b'c'X'ZX | aa'Y'b'c'X'ZX,
X	—	aa'b'c' | aa'Y'b'c' | aa'b'c'X' | aa'Y'b'c'X',
X'	—	bc' | bc'X',
Y	—	aa' | aa'Y',
Y'	—	bc'ZXa'a' | bc'X'ZXa'a' | bc'ZXa'a'Y' | bc'X'ZXa'a'Y',
Z	—	c | cZ',
Z'	—	cb' | cZ'b' | cb'Z' | cZ'b'Z',
a'	—	a,
b'	—	b,
c'	—	c }.
IB102 - úkol 10 - řešení
Odevzdání: 6.12. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [3 body] O nasledujúcich jazycích rozhodnete, zda jsou bezkontextove, a sve rozhodnutí dokazte. (V prípade, ze jazyk je bezkontextový, nam bude jako důkaz stacit napsání príslušne bezkontextove gramatiky nebo zasobníkoveho automatu.)
(a) Li = {w | w E {a, b}+, #„(w) = #6(w)}2
(b) L2 = {w2 I w E {a, b}+, #a(w) = #b(w)}
Řešení: Jazyk L1 je bezkontextový, jazyk L2 není bezkontexový.
Ad (a): Staď si uvedomit, ze se jazyk L1 dí ekvivalentne napsat takto:
Li = {u • v I u,v E {a, b}+, #a(u) = #b(u), #a(v) = #6(v)}
Jední se tedy o jazyk, jehoz slova jsou vzdy zretezením dvou neprázdnách slov, z nichz kazde mí stejní pocet a jako b. Tento jazyk generuje napr. gramatika G = ({S, X}, {a, b}, P, S), kde
P = {   S  — XX,
X  —  XX I aXb I bXa | ab | ba }.
Ad (b): Jazyk L2 je jazyk vsech slov, ktera se dají rozdelit na dve stejné císti, které mají stejní pocet a jako b. (Jazyk L2 se tedy od jazyka L1 znacne lisí, napr. abba E L1, zatímco abba E L2.) Ze je jazyk L2 neregularní, dokízeme pomocí Pumping lemmatu pro bezkontex-tovíe jazyky.
• Necht' n je libovolne, nadíle pevne.
• Zvolíme slovo z E L, Iz| > n takto: z = anbnanbn.
• Vsechna mozna rozdelení z = uvwxy takoví, ze vx = e, IvwxI < n jsou jednoho z techto druhu:
— vwx E {a}+. Volbou i = 0 pak slovo uv°wx°y je bud' tvaru ambnanbn nebo tvaru anbnambn, kde m < n. Tato slova nepatrí do L2.
— vwx E {b}+. Podobne jako v prédchozím bode volbou i = 0 bude slovo uv°wx°y bud' tvaru anbmanbn nebo tvaru anbnanbm, kde m < n. Tato slova opet nepatrí do
L2.
— vwx E {a}+ • {b}+. Pak bud' u E {a}* (vwx je v první polovine slova z) nebo y E {b}* (vwx je v druhe polovine slova z), obe moznosti zíroveň nastat nemohou. Zvolíme opet i = 0, v prvním prípade pak bude slovo uv°wx°y tvaru akblanbn, v druhem prípade tvaru anbnakb1, kde v obou pn'padech alespon jedno z l, k je císlo mensí nez n. Zídne takove slovo nepatri do L2.
— vwx E {b}+ ■ {a}+ (tj. vwx je na rozhraní dvou polovin slova z). Znovu volíme i = 0. Slovo uv°wx°y pak je určite tvaru anbrasbn, kde alespoň jedno z r, s je menší nez n, a tudíž nepatrí do L2.
• Jiná rozdelení nejsou. Ukazali jsme tedy, že pro každe rozdelení je možno najít konstantu i takovou, ze uvlwxly E L2. Podle PL pro bezkontextove jazyky tedy L2 není bezkontextoví. □