Journal articleMEDUNA Alexander and ZEMEK Petr. Generalized OneSided Forbidding Grammars. International Journal of Computer Mathematics. 2013, vol. 90, no. 2, pp. 172182. ISSN 00207160. Available from: http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703  Publication language:  english 

Original title:  Generalized OneSided Forbidding Grammars 

Title (cs):  Zobecněné jednostranné zakazující gramatiky 

Pages:  172182 

Place:  GB 

Year:  2013 

URL:  http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703 

Journal:  International Journal of Computer Mathematics, Vol. 90, No. 2, GB 

ISSN:  00207160 

DOI:  10.1080/00207160.2012.723703 

Keywords 

formal languages, regulated rewriting, generalized onesided forbidding grammars, language families, generative power 
Annotation 

In generalized onesided forbidding grammars (GOFGs), each contextfree rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary contextfree rules without any forbidding strings characterize the family of contextfree languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of contextfree languages.

BibTeX: 

@ARTICLE{
author = {Alexander Meduna and Petr Zemek},
title = {Generalized OneSided Forbidding Grammars},
pages = {172182},
journal = {International Journal of Computer Mathematics},
volume = {90},
number = {2},
year = {2013},
ISSN = {00207160},
doi = {10.1080/00207160.2012.723703},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=9842}
} 
