Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 315

and C → bA 3 A 2 A 1 A 3 A 3 A 2 C | aA 2 A 1 A 3 A 3 A 2 C | cA 1 A 3 A 3 A 2 C | bA 3 A 2 CA 1 A 3 A 3 A 2
CA 3 A 2 C | aA 2 CA 1 A 3 A 3 A 2 C | cCA 1 A 3 A 3 A 2 C | bA 3 A 3 A 2 C | aA 3 A 2 C
Step 4. Since, grammar has no more non GNF productions hence we reach to end and
process stop.
(All GNF productions are shown by bold productions)

11.12 PUMPING LEMMA FOR CONTEXT FREE LANGUAGES

In chapter 10 we have studied the lemma for the testing certain language is regular or not, like
that here we study a similar type of lemma which is called the lemma for context free lan-
guages. On the basis of this lemma we must insure that for a sufficiently long string of a CFL
we can find small sub strings that can be pumped. That is, pumping as many copies of the
substrings yields strings will be in the language.
So, before deriving the pumping lemma for CFL we will study the nature of its parse
tree. One advantage of the conversion of CFG into CNF is to turn the parse tree into binary
tree with following fact,

Fact

If a CFG is in CNF and the length of the largest path in a derivation tree is n then the terminal
string derived in the tree have length ≤ 2 n–1.

Proof

In CNF the possible forms of productions are
A → a or A → BC
and their derivation trees are shown in Fig. 11.25 (a) & (b)

(a root and one leaf node)

A

a
Fig. 11.25(a)
Here length of the largest path is one (n = 1) so the derived string length is 1. Since 21–1 = 1
that is symbol ‘a’ in this case, fact is true.

BC

A

(–1)k

TB TC

≤ 2 k–2 ≤ 2 k–2

Fig. 11.25(b)