From left-regular to Greibach normal form grammars

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)
    169 Downloads (Pure)

    Abstract

    Each context-free grammar can be transformed to a context-free grammar in Greibach normal form, that is, a context-free grammar where each right-hand side of a prorfuction begins with a terminal symbol and the remainder of the right-hand side consists of nonterminal symbols. In this short paper we show that for a left-regular grammar G we can obtain a right-regular grammar G’ (which is by definition in Greibach normal form) which left-to-right covers G (in this case left parses of G’ can be mapped by a homomorphism on right parses of G. Moreover, it is possible to obtain a context-free grammar G��? in Greibach normal form which right covers the left-regular grammar G (in this case right parses of G��? are mapped on right parses of G).
    Original languageUndefined
    Article number10.1016/0020-0190(79)90109-1
    Pages (from-to)51-55
    Number of pages5
    JournalInformation processing letters
    Volume9
    Issue number1
    DOIs
    Publication statusPublished - 20 Jul 1979

    Keywords

    • IR-66922
    • EWI-9212

    Cite this