A survey of normal form covers for context-free grammars

Anton Nijholt

doi:10.1007/BF00264257

A survey of normal form covers for context-free grammars

Anton Nijholt

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

123 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 language	English
Pages (from-to)	271-294
Number of pages	24
Journal	Acta informatica
Volume	14
Issue number	3
DOIs	https://doi.org/10.1007/BF00264257
Publication status	Published - Sep 1980

Keywords

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

Access to Document

10.1007/BF00264257

actaInf1980Final published version, 1.09 MB

Cite this

@article{e40fc9f3b1bd47e18464baa5faddb80c,

title = "A survey of normal form covers for context-free grammars",

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.",

keywords = "EWI-9218, IR-66927, HMI-SLT: Speech and Language Technology",

author = "Anton Nijholt",

year = "1980",

month = sep,

doi = "10.1007/BF00264257",

language = "English",

volume = "14",

pages = "271--294",

journal = "Acta informatica",

issn = "0001-5903",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - A survey of normal form covers for context-free grammars

AU - Nijholt, Anton

PY - 1980/9

Y1 - 1980/9

N2 - 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.

AB - 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.

KW - EWI-9218

KW - IR-66927

KW - HMI-SLT: Speech and Language Technology

U2 - 10.1007/BF00264257

DO - 10.1007/BF00264257

M3 - Article

VL - 14

SP - 271

EP - 294

JO - Acta informatica

JF - Acta informatica

SN - 0001-5903

IS - 3

ER -

A survey of normal form covers for context-free grammars

Abstract

Keywords

Access to Document

Fingerprint

Cite this