IB102 - úkol 8 - řešení
Odevzdání: 28.11. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Mějme následující jazyk nad abecedou {a,b,c,d}:
L = {anbmcrď | n + m = r + s nebo n = s}
Sestrojte jednoznačnou bezkontextovou gramatiku generující tento jazyk. Stručně zdůvodněte, proč je Vaše gramatika jednoznačná.
(Pokud nevíte, jak sestrojit jednoznačnou gramatiku, zkuste sestrojit alespoň nějakou bezkontextovou gramatiku generující tento jazyk. V tom případě bude Vaše řešení hodnoceno maximálně 1 bodem.)
Řešení: Hledaná gramatika může vypadat například takto: G = ({S, B, C, X, Y, Z}, {a, b, c, d}, P, S), kde
P = {   S -> aSd \ B \ C \ BC \ bXd | aYc | e,
B 6 | 65,
C -> c\cC,
X -> bXd | Z,
Y -> aYc | Z,
Z bZc\e }.
Zdůvodnění jednoznačnosti této gramatiky je následující:
Nejprve se podíváme na slova tvaru anbmďds, kde n = s. Zřejmě se při odvození takovýchto slov nikdy nepoužije pravidlo S —> bXd ani pravidlo S —> aYc, protože po jejich použití už nikdy není počet a a d ve větné formě stejný. Slovo tvaru anbmďds, kde n = s, tedy musí vzniknout právě jedním z těchto odvození:
• S ^n anSdn =>■ anBCdn ^* anbmďdn (pokud m > 0 a r > 0)
• S ^n anSdn =>■ anBdn ^* anbmdn (pokud m > 0 a r = 0)
• S ^n anSdn =>■ anCdn ^* anďdn (pokud m = 0 a r > 0)
• S ^n anSíT =>• antT (pokud m = r = 0)
Protože odvození B ^ bm (m > 0) i odvození C =>• cr (r > 0) je vždy jenom jedno (pro dané m nebo r), znamená to, že pro každé slovo tvaru anbmďds, kde n = s, existuje právě jeden derivační strom.
Odvození slov tvaru anbmďds, kde n<sa.n + m = r + s, musí nutně vypadat takto:
S ^n anSdn => anbXdn+1 ^* anb3-nXď => anb3-nZď ^* anbs-'n+rZďď => anb3-n+rďď
a odvození slov tvaru anbmďds, kde n>sa.n + m = r + s, musí nutně vypadat takto:
S ^n asSds => as+1Ycds ^* anYcn-sds => anZcn-sds ^* anbmZcn~s+mď => anbmcn-s+mds
V obou případech jde zřejmě o jedno jediné možné odvození, pro každé slovo tvaru anbmďds, kde n^sa.n + m = r + s, existuje tedy právě jeden derivační strom.
IB102 - úkol 8 - řešení
Odevzdání: 28.11. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Mějme gramatiku G = ({S, A, B, C, D, E, F}, {a, b, c}, P, S), kde
P = {   S -> A | CD | F,
A —ř BA | CAD,
B b | bb,
C -> e | CD,
D -> e j D,
E -> aE\bCb\ cFc,
F ab\ aDaDaS | EC }.
Sestrojte vlastni gramatiku C bez jednoduchých pravidel takovou, že L (G) = L(G'). K jejímu sestrojení použijte algoritmů z přednášky.
Řešení: Nejprve odstraníme nenormované a nedosažitelné neterminály. Při napočítání normovaných neterminálů postupně dostáváme: Ni = {B,C, D, F}, N2 = {B,C, D, F, E, S}, N3 = N2 = Ne. Při počítání dosažitelných neterminálů dostáváme: ÍVq = {S}, Nľ = {S, C, D, E, F}, N2 = Ni = N'. Nová gramatika tedy vypadá takto: G1 = ({S, C, D, E, F}, {a, b, c}, P1,S), kde
P1 = {   S -+ CD\F,
C -> e | CD,
D -> e j D,
E -> aE\bCb\ cFc,
F ab\ aDaDaS \ EC }.
Dále odstraníme e-pravidla. Nejprve napočítáme Ne = {C, D, S} a potom podle algoritmu z přednášky dostaneme následující gramatiku: G2 = ({S', S, C, D, E, F}, {a, b, c}, P2, S'), kde
P2 = {  S' -> S\e,
S -> CD | F | C | D,
C -> CD | C | D,
D -+ D,
E -> aE\bCb\ cFc \ bb,
F —^ ab | aDaDaS \ EC \ aaDaS \ aDaaS \ aDaDa | aaaS \ aDaa | aaDa \ aaa \
Tím nám mohly vzniknout (a taky vznikly) zbytečné neterminály takže je před dalšími úpravami opět odstraníme. Zřejmě N" = {S', E, F, S} je množina normovaných a dosažitelných neterminálů G2, Dostáváme tedy gramatiku: g3 = ({5", S, E, F}, {a, b, c}, P3, S'), kde
P3 = {   S' S\e,
S -> F,
E -> aE\cFc\ bb,
F —^ ab I aaaS \ aaa \ E }.
Dále odstraníme jednoduchá pravidla. Zřejmě N's = {S', S, F, E}, N$ = {S,F,E}, Ne = {E}, Np = {F,E}. Provedením algoritmu z přednášky dostáváme gramatiku: G4 = ({S', S, E, F}, {a, b, c}, P4, S'), kde
Pa = {   S' —> e | aE \ cFc \ bb \ ab \ aaaS \ aaa,
S —> aE | cFc | bb \ ab | aaaS \ aaa,
E -> aE | cFc | bb,
F —> aE \ cFc \bb\ab\ aaaS \ aaa }.
Tím nám mohly vzniknout nedosažitelné neterminály. Snadno se ale ověří, že množina dosažitelných neterminálů gramatiky G4 je N'" = {S',S,E,F}, a tedy výsledná gramatika je G' = G4.