zbMATH — the first resource for mathematics

Context-free-like forms for the phrase-structure grammars. (English) Zbl 0652.68095
Mathematical foundations of computer science 1988, Proc. 13th Symp., Carlsbad/Czech. 1988, Lect. Notes Comput. Sci. 324, 309-317 (1988).
Summary: [For the entire collection see Zbl 0643.00024.]
Some new normal forms for the phrase-structure grammars are presented. Each phrase-structure grammar can be replaced by an equivalent grammar with all of the rules context-free, of the form $$S\to v$$, where S is the initial symbol, and either two extra rules AB$$\to \epsilon$$, CD$$\to \epsilon$$, or two extra rules AB$$\to \epsilon$$, CC$$\to \epsilon$$, or two extra rules AA$$\to \epsilon$$, BBB$$\to \epsilon$$, or even a single extra rule ABBBA$$\to \epsilon$$, or a single extra rule ABC$$\to \epsilon$$.

MSC:
 68Q45 Formal languages and automata