Normal Forms of Context-Free Grammars
摘要
In context-free grammars, the left-hand part of every production is a nonterminal symbol, while the right-hand part comprises terminals as well as nonterminals, of any length and order. These variable length productions, when used in parsing, may produce ever-expanding parse trees, adding to excessive complexity in the parsing algorithms. However, these grammars can be transformed into standard forms: either to Chomsky Normal Form (CNF) or to Greibach Normal Formal (GNF), which have only linear time complexities, while their generating capability of language strings remains the same. A normalized form of grammar is useful in many proofs related to some interesting properties of context-free grammars. This chapter presents simplifications of context-free grammars, which are prerequisites for normalization, and the proofs that show that normal forms of the grammars generate the same language as the original one. The pumping lemma for context-free languages is presented along with worked-out problems. In addition, self-review questions along with the number of classified exercises at the chapter end, are aimed to make overall learning an interesting one.