Mathematical Foundation of Computer Science

DHARM

298 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

II. (q 1 , b b a a, AAZ 0 )  (q 1 , b a a, BAAZ 0 )  {(q 1 , a a, BBAAZ 0 ), (q 2 , a a, AAZ 0 )}
II′ II′′
From ID II′ following are the moves,
(q 1 , a a, BBAAZ 0 )  (q 1 , a, ABBAAZ 0 )
 {(q 1 , ∈, AABBAAZ 0 ), (q 2 , ∈, BBAAZ 0 )
××
Since both these moves don’t empty the stack hence by this path string w is not accepted.
From ID II′′ following are the moves,
(q 2 , a a, AAZ 0 )  (q 2 , a, AZ 0 )  (q 2 , ∈, Z 0 )  (q 2 , ∈, ∈) Accepted

11.9 Simplification of Grammars...........................................................................................

In the previous section we have studied Context free grammars, derivation trees and the gen-

eration of languages from CFG the context free languages. In this section we will study the

simplification of the grammars including simplification of CFGs.

The simplification of grammar means to perform certain operations over its set of pro-

duction/s so that it may reach to some standard form (normal form) of the grammar. So before

going to study the normal form of a grammar first we discuss the preliminary means of simpli-

fication of the grammar. In the chapter we generally restrict our self and discuss the simplifi-

cation of context free grammars. In fact, the means of simplification that are discussed below

are equally useful for the simplification of are other type of grammars.

The means of simplification are as follows,

1. Remove all null production/s


2. Remove all useless production/s


3. Remove all unit production/s


4. Remove all useless symbol/s
   Now we will discuss each means of simplification in details.


5. Remove all null productions
   A production is said to be null production if it derives a null string (∈). For example, produc-
   tion A → ε is a null production where, A is a non terminal and ∈ is a variable/terminal.
   All non terminals that derive the string ∈ in one/more steps of derivation are called
   nullable non terminals of a grammar viz.

l If X ⇒N ∈ then X is nullable.

l If A → ∈ is a production then A ⇒ ∈, so A is nullable.
l If A → B and B → ∈ are the productions then A ⇒ B ⇒ ∈ and B ⇒ ∈, so A and B are
nullable.
l If A → BC and B → ∈ and C → ∈ are the productions then all non terminals A, B and
C are nullable.
By eliminating the null productions it is likely to increase the number of productions in
the grammar. (The ambiguity characteristic of the grammar remain unaltered)