Simplification Of Cfg

THEOREM: Let G = (V, T, S, P) be a CFG. There exists an equivalent grammar G$ = (V$,T$, S, P$ ) that does not contain any useless variables or productions.

Procedure: The first Part-A is to find G1 using the algorithm.

Step 1:Set V1 to Æ

Step 2:Repeat the following step until no more variables are added to V1.

For every AÎV for which P has a production of the form.

Step 3:Take P1 as all the productions in P whose symbols are all in (V1 ÈT ) . Thus the gram mar G1 can be gen erated from G by the above algorithm. Here G1 = (V1, T2, S, P1 ) such that V1 contains only variables A for which

A=>wÎT * *

The next step is to check whether every A for which AÞw = ab *. . . .  isadded to V1 before the procedure terminates.

Step below describes the second Part B.

“Dependency graph” is drawn to find all the variables that cannot be reached from the start symbol S. These variables are removed from the variable set and also all the productions involving the variables. The resultant obtained is G.

Empty Production Removal: The productions of context-free grammars can be coerced into a variety of forms without affecting the expressive power of the grammars.

If the empty string does not belong to a language, then there is a way to eliminate the productions of the form A® l from the grammar. If the empty string belongs to a language, then we can eliminate l from all productions save for the single production S ® l. In this case we can also eliminate any occurrences of S from the right-hand side of productions.

Let us illustrate this through the Example 2.4.4. Any production of a CFG of the form A-> l is called a l-production. Any variable A for which the derivation AÞ* l is possible is called “NULLABLE”. Let G be any CFG with l not in L(G). Then there exists an equivalent grammar $ G having no l-productions.

Procedure to find CFG without ʎ-Productions

Step (i):For all productions A-> l, put A into VN.

Step (ii):Repeat the following steps until no further variables are added to VN.

For all productions

B -> A1 A2 An . . . .  .

where A1 , A2 , A3 , . . . , An  are in VN, put B into VN. To find $P, let us consider all productions in P of the form

A m -> x1 x2 . . . .  xm   m ³ 1

for each xi ÎV  ÈT .

For each such production of P, we put into $P that production as well as all those generated by replacing nullable variables with l in all possible combinations.

(If all xi are nullable, the pro duction A-> l is not put into $P).

Let us illustrate this procedure through an example as shown in example 2.4.5.