Context-free-like forms for the phrase-structure grammars. (English) Zbl 0652.68095

Geffert, Viliam

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

Keywords:

normal forms; phrase-structure grammars