Past exam question: 2081 Chaitra (Regular), Q3(b)
Open in the Padhaiko appQuestion
Convert the following CFG, into CNF: where , , and is starting symbol.
Solution
Elimination of Epsilon Productions: Given grammar rules:
- Identify Nullable Variables:
- is nullable.
- is nullable.
- is nullable. Since start symbol is nullable, we introduce a new start symbol .
- Eliminate from and :
- From : when , we obtain . So .
- From : when , we obtain . So .
- From : remains .
- New start symbol productions: .
Elimination of Unit Productions and Useless Symbols: Eliminating Unit Productions:
- Unit productions: , , .
- Replace with the non-unit productions of : .
- Replace with the non-unit productions of : .
- Thus, .
- Replace similarly:
Eliminating Useless Symbols:
- Generating symbols: (generating), (generating), (generating). All symbols generate terminal strings.
- Reachable symbols: reaches and (and , reach each other), but no rule mentions any more: once was replaced, became unreachable.
- So is useless and is deleted with its rules. The remaining grammar is
Conversion into Chomsky Normal Form: Introduce non-terminals for terminal symbols:
Convert rules of length into binary non-terminal form:
- For :
- with
- For :
- with
- For :
Final CNF Grammar:
Answer:
Eliminating -productions gives and , removing unit productions gives (after which is unreachable and is dropped), and introducing variables produces the final grammar in Chomsky Normal Form.