Chapter 6. Simplifications of CFGs

6.1 Methods for transforming grammars

Substitution Rule

• Equivalent Grammar를 만드는데, 한 변수를 제거하는 목적

1. Removing λ-productions
2. Removing unit productions
3. Removing useless productions

--> Good for Parsing

6.2 Normal Forms for CFGs

1. Chomsky Normal Form (CNF)

   1) RHS has 2 Variables
   2) RHS has a Symbol

2. Greinbach Normal Form (GNF)

   1) RHS has a symbol and Variabels_k (k>=0)

6.3 Membership algorithm for CFG

• CYK Algorithm