A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
Sheila A. Greibach · Journal of the ACM · 1965
A context>free phrase structure general~or is in..~landard jb~'m if and only if alt of its rules are of the form: Z -, aY~, ... , Y,~ where Z and Yi are intermediate symbels and a is a l~erminM symbol, so that one input., symbol is processed at each s-tep.Standard form is eonvenien(~ for computer manipulation of eontext-free languages.A proof is given that every context-free phrase structure generator is strongly equivalent to one in standard form; it, is in the form of an algorithm now being prograrr~med, and offers an independent proo[' of a variant of the Chomsky-Setditzenberger 1tortoni form theorem.