Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 309

C → abCa | aDb

D → bD | aC

Sol. Since grammar G uses the non terminals {S, A, B, C, D} and terminals {a, b}.

We test the non terminals; and find the active non terminals and drop non active ones

i.e.

l D ⇒ bD or D ⇒ aC never terminates on terminals so non active;

l C ⇒ abCa or C ⇒ aDb ⇒ never terminates on terminals so non active;

l B ⇒ bbA ⇒ bba; so active non terminal.

l A ⇒ a; so active non terminal.

l S ⇒ AB ⇒ terminated on terminals because both A and B are active; so active one.

Since, {S, A, B} are only active non terminals so the productions defined and using these

symbols are

S → AB

A → aAb | bAa | a

B → bbA | aaB | AB

Now, we test the reachability of the symbols used in grammar G.

l Symbols A and B are reachable because S ⇒ AB.

l Symbol a and b are also reachable because S ⇒ AB ⇒ aAbB and so on.

Hence, all symbols used in the previous simplified step of grammar{S, A, B, a, b} are

reachable symbols.

So, the simplified grammar with no useless symbols is

S → AB

A → aAb | bAa | a

B → bbA | aaB | AB

11.10 CHOMSKY NORMAL FORM (CNF)

Let G be the context free grammar then we find another context free grammar G′ such that all
productions in G′ are either of forms:
l A → a, where A is non terminal and a is a terminal, or
l A → BD, where A, B and D are non terminals.
and L(G′) = L(G) – {ε} means grammar G′ is free from null productions then grammar G′ is said
to be in Chomsky Normal Form (CNF).
To obtain the CFG in CNF we apply the means of simplification 1 to 4, such that gram-
mar is free from null productions, useless productions, unit productions and useless symbols.
Now, the remaining productions of the context free grammar are of form α → β that is
either,
l where α is a non terminal (∈ VN) and β is a terminal (∈ VT) or, a allowed form of CNF
l | β | ≥ | α | or β contains two or more symbols i.e.
n if one is terminal and other is non terminal then replace the terminal symbol by
a new non terminal viz.