IB102 - úkol 9, příklad 1
Odevzdání: 26.11. 2012
Vypracoval (a): UČO: Skupina:
1. [2 body] Převeďte následující bezkontextovou gramatiku do Chomského normální formy.
G = ({S, A, B, C, D, E, F, G}, {a, b, c}, P, S)
P = {   S  ->  aSc | bDc | D, A —>  aEc | aFEc, B —>  aSc | e, C  -+ bFc, D  ->  bDc \ G\e, E  ->•  aAc | AB, F  -> bcG, G  ->  6c | AE}
Rešení:
1. Z gramatiky odstraníme nepoužitelné symboly:
• Normované neterminály jsou: B, D, G, S, F, C. Odstraníme neterminály A, E.
G = ({S, B, C, D, F, G}, {a, b, c}, P, S)
P = {   S  ->  aSc | bDc | D, B —>  aSc | e, C  -+ bFc, D  ->  bDc \ G\e, F  -> bcG, G  -+ bc}
• Dosažitelné neterminály jsou: S, D, G. Odstraníme neterminály B, C, F.
G = ({S,D,G},{a,b,c},P,S)
P = {   S  ->  aSc | bDc | D, D        bDc \ G\e, G  ^ bc}
2. Odstraníme epsilon-pravidla: Ne = {S, D}.
G= ({S',S,D,G},{a,b,c},P,S)
P = {  S' -> S\e,
S —> aSc | ac \ bDc \ bc\ D,
D -> bDc\bc\ G,
G -+ bc}
3. Odstraníme jednoduchá pravidla: N$' = {S', S, D, G}, N$ = {S, D, G}, = {D, G}, Nq {G}.
G= ({S',S,D,G},{a,b,c},P,S)
P = {   S' —>  ac\ aSc | bc \ bDc \ e, S —>  aSc | ac \ bDc \ bc, D —>  bDc | bc, G  -+ bc}
Následně odstraníme nedosažitelné neterminály, tj. neterminál G:
G = ({S',S,D},{a,b,c},P,S)
P = {   S' —>  ac | aSc | bc | bDc | e, S —>  aSc | ac \ bDc \ bc, D        bDc | bc}
4. Provedeme samotný převod do CNF.
G = ({S', S, D, G, A, B, C, X, Y}, {a, b, c}, P, S)
P = {  S' AC | AX | BC | BY \ e,
S -+ AC j AX j BY j BC,
D -> BC | BY,
A —^ a,
B -+ b,
C -+ c,
X -+ sc, Y  -+ DC}