21 0 .~ Theory of Computer Science
given grammar has no null productions and is in CNF we need not carry out
step 1. So we proceed to step 2.
Step 2 (i) AI-productions are in the required fonn. They are Al ~ A 2 A 2 1 a.
(ii) A 2 ~ b is in the required fonn. Apply Lemma 6.1 to A 2 ~ AjA j.
The resulting productions are A 2 ~ A 2 A 2 A I , A 2 ~ aA I • Thus the
ATproductions are
A 2 ~ A 2 A 2 Aj,
A 2 ~ aA],
Ao ~ b
Step 3 We have to apply Lemma 6.2 to ATProductions as we have
A 2 ~ A 2 A 2 A l' Let Z2 be the new variable. The resulting productions are
A 2 ~ aAI,
A 2 ~ b
Z2 ~ ih4 I ,
Z2 ~ A 2 A I Z 2 ·
Step 4 (i) The A 2 -productions are A 2 ~ aAjl bl aA I Z 2 1 bZ 2 ·
(ii) Among the A j-productions we retain A j ~ a and eliminate
A j ~ A 2 A 2 using Lemma 6.1. The resulting productions are AI ---t aA I A 2 IbA:>
AI ~ aA I Z 2 A 2 IbZ 2 A:> The set of all (modified) AI-productions is
A j ~ alaAIA2IbA2IaAIZ2A2IbZ::A2
Step 5 The ZTproductions to be modified are Z2 ~ A 2 A I , Z2 ~ A 2 A jZ 2 ·
We apply Lemma 6.1 and get
Z2 ~ aAIA] IbAil aA I Z2A 1 IbZ 2 A I
Z2 ~ aA I A j Z 2 1 bA j Z 2 1 aA J Z 2 Aj Z 2 1 bZ 2 A I Z 2
Hence the equivalent grammar is
G' = ({AI' A 2 , Z2}, {a, b}, P], AI)
where PI consists of
AI ~ a I aA]A 2 1 bA 2 1aA IZ2A I I bZ 2 A 2
A~ ~ aA j iblaA I Z 2 1bZ 2
Z2 ~ aA]AII bA] IaA 1 Z 2 A I IbZ 2 A j
Zo ~ aA J A]Z21 bA I Z 2 1 aA I Z 2 A I Z 2 1 bZ 2 A]Z2
EXAMPLE 6.16
Convert the grammar S ~ AB, A ~ BS Ib, B ~ SA Ia into ONF.
Solution
As the given grammar is in CNF, we can omit step 1 and proceed to step 2
after renaming S, A. B as AI, A 2 . A 3 , respectively. The productions are AI ~
A 2 A 3 • A 2 ~ A011 b, A 3 ~ A j A 2 1 a.