A survey of normal form covers for context-free grammars

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)
    75 Downloads (Pure)

    Abstract

    An overview is given of cover results for normal forms of context-free grammars. The emphasis in this paper is on the possibility of constructing ɛ-free grammars, non-left-recursive grammars and grammars in Greibach normal form. Among others it is proved that any ɛ-free context-free grammar can be right covered with a context-free grammar in Greibach normal form. All the cover results concerning the ɛ-free grammars, the non-left-recursive grammars and the grammars in Greibach normal form are listed, with respect to several types of covers, in a cover-table.
    Original languageEnglish
    Pages (from-to)271-294
    Number of pages24
    JournalActa informatica
    Volume14
    Issue number3
    DOIs
    Publication statusPublished - Sep 1980

    Keywords

    • EWI-9218
    • IR-66927
    • HMI-SLT: Speech and Language Technology

    Fingerprint Dive into the research topics of 'A survey of normal form covers for context-free grammars'. Together they form a unique fingerprint.

    Cite this