SKEDSOFT

Automata | Comp. Sc. Engg.

Simplification of CFG-Introduction: In a Context Free Grammar (CFG), it may not be necessary to use all the symbols in V ÈT, or all the production rules in P while deriving sentences. Let us try to eliminate symbols and productions in G which are not useful in deriving sentences.

Let G = (V,T, S, P) be a context-free grammar. Suppose that P contains a production of the form

Assume that A and B are different variables and that

B -> y1 | y2 |. . . | yn |.

is the set of all productions in P which have B as the left side.

Let be the grammar in which P is constructed by deleting

A-> x1  B x 2

from P, and adding to it

Substitution Rule: A production A® x Bx 1 2 can be eliminated from a grammar if we put in its place the set of productions in which B is replaced by all strings it derives in one step. In this result, it is necessary that A and B are different variables.

Abolishing Use less Productions: In the grammar G with P,

the production S -> A does not play any role because A cannot be transformed into a terminal string. ‘A’ can occur in a string derived from S, this can never lead to a sentential form. Hence this production rule can be removed, which does not affect the language.

Definition: Let G = (V,T, S, P) be a CFG.

A variable AÎV is said to be “useful” iff there is at least one wÎL(G) such that

with x, y in (V ÈT )* , i.e., a variable is useful iff it occurs in at least one derivation.

Illustration: Consider the grammar G with P

Here the variable B is said to be “useless”, hence the production B® bA is also “useless”. There is no way to achieve S ÞxBy * .