IB102 - úkol 9 - řešení
Odevzdání: 29.11. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [2 body] Mejme následující jazyk:
L = [w G [a, b}* | w = wR} U [w G [a, b}* | #0(w) mod 2 = #b(w) mod 2}
Sestrojte jednoznačnou bezkontextovou gramatiku generující jazyk L. StruCne vysvetlete, proC je Vase gramatika jednoznaCna.
Rešenŕ: Zrejme umíme sestrojit jednoznaCnou gramatiku pro [w g [a, b}* | w = wR} (jazyk všech palindromu) i pro [w g [a, b}* | #«(w) mod 2 = #b(w) mod 2} (jazyk všech slov se stejnou paritou symbolu a a b). Sjednocení techto jazyku ale není disjunktní. Budeme se tedy nejprve snazit napsat L jako disjunktní sjednocení dvou jazyku, pro které umíme sestrojit jednoznacne gramatiky.
Pouzijeme nasledující ívahu: Vsechny palindromy sude delky spMují podmínku stejne parity a a b, zatímco zídny palindrom liche delky tuto podmínku nesplňuje. Jazyk L muzeme tedy ekvivalentne napsat takto:
L = [w g [a, b}* | w = wR, |w| je lichí} u [w g [a, b}* | #«(w) mod 2 = #b(w) mod 2}
Hledaní gramatika je tedy napr. G = ([S, X, Y00, Y01, Yw, Yn}, [a,b},P,S), kde
[ s		X | y00,	
X		a | b | aXa |	bXb,
y00		ay10 | by01 |	
Y01		ay11 | by00,	
Y10		ay00 | by11,	
Y11		ay01 | by10 |	
(Zde neterminal X generuje príve vsechny palindromy liche delky a neterminíl Y00 generuje prave vsechna slova se stejnou paritou a a b.)
IB102 - úkol 9 - řešení
Odevzdání: 29.11. 2010
Vypracoval: James Bond Skupina: MI6
UCO: 007
2. [3 body] Mejme gramatiku G = ({S, A, B, C, D, E, F}, (a, b, c}, P, S), kde
S	—	AB | cC,
A	—	e | aA | SEb,
B	—	e | bB | AEc,
C	—	D | AcB,
D	—	Bb | Abc | C,
E	-	abE | Ec | E F,
F	—	Ea | ba }.
Ke gramatice G sestrojte (použitím algoritmu z prednášky) ekvivalentní gramatiku v Chomskeho normálni forme.
Poznámka: Gramatika v CNF musí bát vždy redukovana.
Rešenŕ: Nejprve z gramatiky odstraníme nepoužitelne symboly (tento krok bychom nemuseli v tuto chvíli delat, je ale váhodne jej provest, protože se tím zbavíme zbytečných castí gramatiky a dale budeme pracovat s mensí gramatikou).
• Normovane neterminaly jsou: Ne = (A, B, F, S, C, D}. (V prvním kroku algoritmu to jsou A, B a F, v druhem se pndají S, C a D, ve tretím kroku se nic nepnda, proto skoncíme.) Odstraníme tedy z gramatiky neterminal E a vsechna pravidla jej obsahující.
S	—	AB | cC
A	—	e | aA
B	—	e | bB
C	—	D | AcB
D	—	Bb | Abc | C
F	->•	ba
• Dosazitelne symboly jsou: N' = (S, A, B, C, D} a S' = (c, a, b}. (V nultem kroku algoritmu to je S, v prvním kroku se pridají A, B, c a C, ve druhem kroku se pridají a, b a D, ve tretím kroku se nepridí nic a proto skoncíme.) Odstraníme tedy z gramatiky neterminíal F.
S	—	AB | cC
A	—	e | aA
B	—	e | bB
C	—	D | AcB
D	—	Bb | Abc | C
Nyní je třeba odstranit e-pravidla. Spočítáme si proto nejprve Ne = {A, B, S} a postupujeme dále podle algoritmu z přednášky (S; je nyní novy počateční neterminal):
S'	—	S | e
s	—	AB 1 cC 1 A 1 B
A	—	aA 1 a
B	—	bB 1 b
C	—	D 1 AcB 1 Ac 1 cB 1 c
D	-	Bb | Abc | C | b | bc
Následně odstraníme jednoduchá pravidla. Nejprve si napočítáme množiny Nx pro všechny neterminály X:
Ns> = {S ',S,A,B } Ns = {S, A, B}
Na = {A} Nb = {B}
Nc = {C, D} Nd = {D,C}
A opet pokračujeme dále dle algoritmu z přednášky:
S'	—	e | AB | cC | aA |	a | bB | b		
S	—	AB | cC | aA | a |	bB | b		
A	—	aA | a			
B	—	bB | b			
C	—	AcB | Ac | cB | c	| Bb | Abc |	b|	bc
D	->•	AcB Ac cB c	Bb Abc	b	bc
Tím nám mohly vzniknout nedosažitelne neterminály (nenormovane neterminály odstranením jednoduchách pravidel vzniknout nemohou). Spočítáme si proto opet množinu dosažitelných neterminálU: [S',A,B,C}. Odstraníme ž gramatiky neterminíly S a D.
S1        e | AB | cC | aA | a | bB | b A        aA | a
B -   bB | b
C —  AcB | Ac | cB | c | Bb | Abc | b | bc
Nyní mužeme prejít k samotnemu prevodu na CNF.
Vísledná gramatika je G' = ([S', A, B, C, (cB), (bc), a', bb, cC}, [a, b, c}, P', S'), kde
P' = { S'
A B C
e | AB | c'C | a'A | a | b'B | b,
— a'A | a,
— b'B | b,
— A{cB) I Ac' I c'B I c I Bb' | A{bc) | b | b'c',
(cB) — c'B,
(bc) — b'd,
a' — a,
b' — b,
d — c }.