Simplification of cfg ppt

THEORY OF COMPUTATION

1. Elimination of Useless Symbols Elimination of Unit productions Elimination of Null Productions Problems related to Simplification of CFG.. SIMPLIFICATION OF CFG

2. CFGs are reduced in two phases Phase 1 − Derivation of an equivalent grammar, G’, from the CFG, G, such that each variable derives some terminal string . Phase 2 − Derivation of an equivalent grammar, G”, from the CFG, G’, such that each symbol appears in a sentential form .

3. Eliminating the useless Symbols

4. Consider: S -> abS | abA | abB A -> cd B -> aB C -> dc Production ‘C -> dc’ is useless because the variable ‘C’ will never occur in derivation of any string. The other productions are written in such a way that variable ‘C’ can never reached from the starting variable ‘S’. Production ‘B -> aB ’ is also useless because there is no way it will ever terminate . If it never terminates , then it can never produce a string. Hence the production can never take part in any derivation.

5. So the modified grammar becomes – S -> abS | abA A -> cd C -> dc Identify all the variables that can never be reached from the starting variable such as variable ‘C’. We then remove all the productions in which variable ‘C’ occurs. The grammar below is now free of useless productions – S -> abS | abA A -> cd

6. Eliminating the Null Production

7. Eliminating the Unit Production