A context-free grammar is in Chomsky normal form when every production has the form or , where are nonterminals and is a terminal symbol; one may additionally allow the new start production when the language contains the empty string, provided never appears on a right-hand side.
The standard conversion proceeds as follows.
- Introduce a fresh start symbol and . This changes only when the old start symbol occurs on a right-hand side or when a protected start symbol is needed to preserve .
- Find all nullable nonterminals, add productions obtained by omitting nullable occurrences, and remove the original -productions except the permitted . This leaves unchanged.
- Eliminate each unit production by adding to the non-unit productions reachable through its transitive closure. This leaves unchanged.
- Delete non-generating symbols and then unreachable symbols. This is the only simplification stage that can shrink .
- In every right-hand side of length at least two, replace a terminal by a fresh nonterminal with . New nonterminals are needed exactly for terminals that occur in such mixed or long productions.
- Break every right-hand side of length at least three into binary productions, introducing fresh nonterminals for successive suffixes. New nonterminals are needed exactly when such long productions remain.
The terminal alphabet may be kept unchanged throughout, although unused terminals may be discarded by convention. Every stage preserves the generated language, with the explicit protection of at the start-symbol stage. For example,is already in Chomsky normal form and generates the infinite language , so its conversion may be the grammar itself.
Articles by others on the same topic
There are currently no matching articles.