Mathematical Foundation of Computer Science

DHARM

332 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

(iii)S → 0S0/1S1/∈
A → 0B1/1B0
B → 0B/1B/∈
(iv)S → abSb/a/aAb, A → bS/aAAb
11.15 Convert CFG into GNF.
(i) Convert the grammar to GNF
S → AA|0
A → SS|1
(ii)S → PQ|0
P → QS|1
Q → PQP|0P|2
11.16 Prove that the grammar for the language L = {0n 1 n 2 n | n ≥ l} is not a context free grammar.
[Hint : Let G is the grammar for L then G has following productions,
S → 0 1 2 | 0 S B 2
2 B → B 2
1 B → 1 1
which is a length increasing grammar]

11.17 Prove that the language L = { 0
n^2
| n ≥ l} is neither a regular language nor a context free lan-
guage.
[Hint : When we construct the grammar for the language L then its grammar must has following
set of productions,
S → 0|CD
C → ACB|AB
AB → 0BA
B0 → 0B
A0 → 0A
AD → D0
BD → E0
BE → E0
E → 0
Which are of type 1-grammar productions. Therefore the language is neither a regular language
nor a context free language]

11.18 Construct the grammar for the language L = { 02 n| n = l}.
[Hint : Similar to exercise 1.17 we can construct the grammar for L that contains following set of
productions,
S → AC0B
C0 → 00C
CB → DB|E
0D → D0
AD → AC
0E → E0
AE → ∈
which is a type 0 grammar]