Simplification of CFG

The simplification of CFG (Context-Free Grammar) involves several steps aimed at eliminating redundant or unnecessary parts of the grammar without changing the language it generates.

The common steps involved in simplification include:

1. Removing Useless Symbols

This involves eliminating symbols (both terminal and non-terminal) that do not contribute to generating any string in the language. This category contains two types:

• Non-generating symbols: These are Non-terminal symbols that cannot be used to derive any terminal string. 
• Non-reachable symbols: These are symbols (Non-terminal or terminal) that cannot be reached from the start symbol of the grammar.

Consider the following CFG, which is designed to generate strings over the alphabet $\{a,b\}$:

• $S\to AB|a$
• $A\to aA|B$
• $B\to b$
• $C\to cC|ϵ$
• $D\to a$

In this grammar:

• $S$ is the start symbol.
• $A$, $B$, $C$, and $D$ are non-terminal symbols.
• $a$ and $b$ are terminal symbols.

Observations

• All symbols $A$, $B$, and $D$ directly or indirectly generate terminal strings.
• $C$ generates $c$ but is never reached from $S$.
• $D$ generates $a$ but is also not reachable from $S$.

So, Removing the non-reachable symbols $C$ and $D,\; we\; get\; simplified\; form\; of\; CFG\; given\; below$

• $S\to AB|a$
• $A\to aA|B$
• $B\to b$

2. Remove Null Production from CFG

Sometimes, some production rules of CFGs contain redundant null (epsilon) moves. In some cases (but not always), We can remove all these redundant Null productions from a CFG.  

IF G1 is the CFG which contains the redundant null moves and G2 is the CFG which is derived from G1 after the removal of redundant null Production, Then 

G1 must be equal to G2 (i.e., G1=G2).

Because any of the two grammars are considered equivalent if they produce the same language.

 Cases to Remove Null Productions

In every case, it is impossible to eliminate a null production from CFG. Let explain all

Case 01:

If the Null (epsilon) move is the part of each string that is derived from a given CFG, then the Null move cannot be removed from that CFG.

Example: Consider a Context-free grammar (G1) with the following production rules

• S → aS | A
• A → ε

After Simplification, Context free Grammar (G2) is given below

• S → aS | a | ε

So, We cannot remove null production from the given grammar (G1) because the Null (epsilon) move is the part of each string derived from the given CFG.

Case 02:

If the Null (epsilon) move is not the part of each string derived from a given CFG, then the Null move can be removed from that CFG.

Example: Consider a CFG with the following production rules

• S → ABC
• A → aA | ε
• B→ bB | ε
• C → c

After Simplification, Context free Grammar (G2) is given below

• S → ABC | BC | AC | C
• A → aA | a
• B→ bB | b
• C → c

We can remove all null production from the given grammar (G1) because the Null (epsilon) move is not part of any string derived from the given CFG. G1 and G2 also generate the same results as well.

3.Removal of Unit Production

Any Production Rule of the form A → B where A and B belong to Non-Terminals is called Unit Production. These Unit Production can be removed from CFG.

Procedure for Removal of Unit Production

Step 01: To remove A→ B, add production A→x to the grammar rule whenever B→x occurs in the grammar where [x belongs to the terminal, x can also be Null]

Step 2: Delete A→B from the grammar.

Step 3: Repeat from step 1 until all unit productions are removed.

Important: IF G1 is the CFG, which contains the Unit Productions, and G2 is the CFG, which is derived from G1 after the removal of Unit Productions, Then. G1 must be equal to G2 (i.e. G1=G2)

 Examples of Remove Unit Productions

Example 01: Remove unit productions from a grammar (G1) whose production rule is given by

P: S→XY, X→a, Y →Z | b, Z→M, M→N, N→a                        // Grammar (G1)

In the above grammar (G1), Unit Productions are

1. Y → | Z
2. Z→ M
3. M → N

The production unit, which is removed easily, is considered first. Let see,

For the Removal of Third Unit Production (M →  N)

As N→a So, Unit Production M → N is updated to M→a.

For the Removal of Second Unit Production (Z → M)

As we derived M→a in above case, So, Unit Production Z → M is updated to Z→a

For the Removal of First Unit Production (Y →  Z)

As we derived Z→a, So, Unit Production Y→Z is updated to Y→a

After Removal Unit Productions, the Updated Grammar (G2) is given below

P: S→XY, X→a, Y →a| b, Z→a, M→a, N→a            // Grammar (G2)

We can remove the unreachable states from the above grammar (G2). So Finally, Grammar (G2) is given below

P: S→XY, X→a, Y →a| b.                                         // Grammar (G2)

Note: Results of G1 and G2 will be similar.

Example 02: Remove unit productions from a grammar (G1) whose production rule is given by

P: S → aA | B, A → ba | bb, B → A | bba                       // Grammar (G1)

In the above grammar, Unit Production is

1. S → B
2. B→ A

The production unit, which is removed easily, is considered first. Let see,

For the Removal of 2^nd Unit Production (B→ A)

As A→ba | bb. So, Unit Production B → A | bba is updated to B→ba | bb.

For the Removal of the first Unit Production (S →  B)

As B→A | ba | bb and A →ba|bb Therefore B→ ba | bb | bba. So,  Unit Production S → B is updated to S→ ba | bb | bba.

After Removal Unit Productions, the Updated Grammar (G2) is given below

P: S → aA | ba | bb | bba, A → ba | bb, B → A | bba                       // Grammar (G1)

We can remove the unreachable states from the above grammar (G2). So Finally, Grammar (G2) is given below

P: S → aA | ba | bb | bba, A → ba | bb                       // Grammar (G2)

Note: Results of G1 and G2 will be similar.

Unreachable states are those states which are not reachable from the initial state.