Publication Details

Phrase-Structure Grammars: Normal Forms and Reduction

KŘIVKA Zbyněk, MEDUNA Alexander and ZEMEK Petr. Phrase-Structure Grammars: Normal Forms and Reduction. The Computer Journal, vol. 59, no. 8, pp. 1180-1185. ISSN 0010-4620.
Czech title
Obecné gramatiky: Normální formy a redukce
Type
journal article
Language
english
Authors
Keywords
formal languages, phrase-structure grammars, normal forms
Abstract
This paper establishes two new normal forms for phrase-structure grammars in which both context-free rules and non-context-free rules are in prescribed forms. In addition, a limit is placed on the number of context-free rules. More specifically, the first form has 2 + n context-free rules, where n is the number of terminals. Concerning non-context-free rules, each of them has the form AB -> CD, where A, B, C, D are nonterminals. The second normal form has always only two context-free rules---S -> S# and # -> e, where S is the start symbol, # is a nonterminal, and e is the empty string. Regarding non-context-free rules, each of them is of the form AB -> XD, where A, B, D are nonterminals and X is a nonterminal or a terminal.
Published
2016
Pages
1180-1185
Journal
The Computer Journal, vol. 59, no. 8, ISSN 0010-4620
Publisher
Oxford University Press
DOI
BibTeX
@ARTICLE{FITPUB9949,
   author = "Zbyn\v{e}k K\v{r}ivka and Alexander Meduna and Petr Zemek",
   title = "Phrase-Structure Grammars: Normal Forms and Reduction",
   pages = "1180--1185",
   journal = "The Computer Journal",
   volume = 59,
   number = 8,
   year = 2016,
   ISSN = "0010-4620",
   doi = "10.1093/comjnl/bxw001",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9949"
}
Back to top