CFG Problem Solve Tip

Problem Solve Tip

• design CFG is like peeling onion - start from right and left side ← cannot effect both side → so represent required string - ex. a^(k+n)b^k c^n → a^n a^k b^k c^k → we can peel n

• CFG only solve add → so make sub to add - ex. a = b - c → b = a + c

• remove lambda → unit → redundant → CNF

1. Remove λ-productions

2. Remove unit productions

3. Remove redundant symbols