Past exam question: 2082 Kartik (Back), Q3(c)(ii)
Open in the Padhaiko appQuestion
Convert the following CFG into CNF. consists of:
and is the start symbol.
Solution
Elimination of Epsilon Productions: A grammar is in Chomsky Normal Form (CNF) if every rule is of the form (two non-terminals) or (single terminal).
- Identify nullable variables: Variable is nullable. is not nullable. For , since is non-nullable, cannot derive .
- Replace occurrences of nullable :
- From , omitting yields: .
- From :
- Retain both :
- Omit first :
- Omit second :
- Omit both : So .
- Productions for : .
Elimination of Unit Productions and Useless Symbols: Eliminating Unit Productions:
- The only unit production is .
- Since , replace by .
- Updated production set:
Eliminating Useless Symbols:
- Generating symbols: (generating), (generating), (generating). All variables generate terminals.
- Reachable symbols: From start symbol , variables and are directly reachable. No useless symbols exist.
Conversion into Chomsky Normal Form: Introduce non-terminals for terminals appearing in composite rules:
Transform each production to binary non-terminal form or single terminal:
- For :
- (already CNF)
- For :
- with
- For :
- (already CNF)
- (already CNF)
- with
Final CNF Grammar:
Answer:
After eliminating -production and unit production , introducing helper variables converts all productions into standard CNF ( or ).