A Survey of Normal form Covers for Regular Grammars

Article type: Research Article

Authors: Nijholt, Anton

Affiliations: Vrije Universiteit, Department of Mathematics, Amsterdam, The Netherlands

Abstract: An overview is given of cover results for normal forms of regular grammars. Due to the special form of regular grammars and due to the results which are obtained it is sufficient to consider covering grammars in Greibach normal form. Among other things it is proved that any left-regular grammar can be left covered with a context-free grammar in Greibach normal form. All the cover results concerning the left- and right-regular grammars are listed, with respect to several types of covers, in a cover table.

Keywords: regular grammars, covers, Greibach normal form, parsing

DOI: 10.3233/FI-1981-4402

Journal: Fundamenta Informaticae, vol. 4, no. 4, pp. 761-776, 1981