Journal articleKŘIVKA Zbyněk, MEDUNA Alexander and ZEMEK Petr. PhraseStructure Grammars: Normal Forms and Reduction. The Computer Journal. Oxford: Oxford University Press, 2016, vol. 59, no. 8, pp. 11801185. ISSN 00104620.  Publication language:  english 

Original title:  PhraseStructure Grammars: Normal Forms and Reduction 

Title (cs):  Obecné gramatiky: Normální formy a redukce 

Pages:  11801185 

Place:  GB 

Year:  2016 

Journal:  The Computer Journal, Vol. 59, No. 8, Oxford, GB 

ISSN:  00104620 

DOI:  10.1093/comjnl/bxw001 

Keywords 

formal languages, phrasestructure grammars, normal forms 
Annotation 

This paper establishes two new normal forms for phrasestructure grammars in which both contextfree rules and noncontextfree rules are in prescribed forms. In addition, a limit is placed on the number of contextfree rules. More specifically, the first form has 2 + n contextfree rules, where n is the number of terminals. Concerning noncontextfree rules, each of them has the form AB > CD, where A, B, C, D are nonterminals. The second normal form has always only two contextfree rulesS > S# and # > e, where S is the start symbol, # is a nonterminal, and e is the empty string. Regarding noncontextfree rules, each of them is of the form AB > XD, where A, B, D are nonterminals and X is a nonterminal or a terminal.

BibTeX: 

@ARTICLE{
author = {Zbyn{\v{e}}k K{\v{r}}ivka and Alexander Meduna and
Petr Zemek},
title = {PhraseStructure Grammars: Normal Forms and
Reduction},
pages = {11801185},
journal = {The Computer Journal},
volume = {59},
number = {8},
year = {2016},
ISSN = {00104620},
doi = {10.1093/comjnl/bxw001},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9949}
} 
