(6.9)
(6.11)
(6.10)
(6.12)
Chapter 6: Context-Free Languages g 211
Step 2 (i) The Aj-production A j ~ A 2 A 3 is in the required form.
(ii) The ATproductions A 2 ~ A~ll b are in the required form.
(iii) A 3 ~ a is in the required form.
Apply Lemma 6.1 to A 3 ~ AjA? The resulting productions are A 3 ~ A2A~2'
Applying the lemma once again to A 3 ~ A2A~2' we get
A 3 ~ A~lA~21 bA 3 A:;.
Step 3 The A 3 -productions are A 3 ~ a 1 bA~2 and A 3 ~ A~jA~:;. As we
have A 3 ~ A~!A~2' we have to apply Lemma 6.2 to A 3 -productions. Let
Z3 be the new variable. The resulting productions are
A 3 ~ a IbAy4 2 , A 3 ~ aZ31 bA~2Z3
Z3 ~ AjA~2'
Z3 ~ AlA~2Z3
Step 4 (i) The ArProductions are
A 3 ~ a 1 bA~:;1 aZ31 bA~:;Z3
(ii) Among the A:;-productions, we retain A:; ~ b and eliminate A:; ~
A ~ j using Lemma 6.1. The resulting productions are
A:; ~ aA] IbA~:;AJiaZ3A IbA~2Z~!
The modified A:;-productions are
A:; ~ b 1 aA!1 bA~:;A!1 aZ~ll bA,A:;Z~]
(iii) We apply Lemma 6.1 to A l ~ A:;A 3 to get
A l ~ bA 3 1aA jA 3 1bAy4:;A 1 A 3 1aZ~jA31 bA~2Z3AjA3
Step 5 The Zrproductions to be modified are
Z3 ~ A]A021 A j A02 Z 3
We apply Lemma 6.1 and get
Z3 ~ bAy4y4.:;1 bAy42Z3
Z3 ~ aA]A~y42IaA]A~y42Z3
Z3 ~ bA~:;A]Ay4y421 bA3A:;AjA~3A:;Z3
Z3 ~ aZ~lA~3A:;1 aZ~]A3A~2Z3
Z3 ~ bA~2Zy4!A3Ay4:;1 bA~:;Z~IA3A3A:;Z3
The required grammar in GNP is given by (6.9)-(6.12).
The following example uses the Remark appearing after Theorem 6.9. In
this example we retain productions of the form A ~ aa and replace the
terni:1als only when they appear as the second or subsequent symbol on
R.H.S. (Example 6.17 gives productions to generate arithmetic expressions
involving a and operations like +, * and parentheses.)