Journal articleMEDUNA Alexander and ZEMEK Petr. OneSided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics. 2012, vol. 89, no. 5, pp. 586596. ISSN 00207160. Available from: http://www.tandfonline.com/doi/abs/10.1080/00207160.2011.642300  Publication language:  english 

Original title:  OneSided Forbidding Grammars and Selective Substitution Grammars 

Title (cs):  Jednostranné zakazující gramatiky a selektivní gramatiky 

Pages:  586596 

Place:  GB 

Year:  2012 

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

Journal:  International Journal of Computer Mathematics, Vol. 89, No. 5, GB 

ISSN:  00207160 

DOI:  10.1080/00207160.2011.642300 

Keywords 

Formal language theory, regulated rewriting, onesided forbidding grammars, selective substitution grammars, generative power 
Annotation 

In onesided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars.
As its main result, the present paper proves that onesided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, the paper proves that onesided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of contextfree languages. In the conclusion, the significance of the achieved results is discussed.

BibTeX: 

@ARTICLE{
author = {Alexander Meduna and Petr Zemek},
title = {OneSided Forbidding Grammars and Selective Substitution
Grammars},
pages = {586596},
journal = {International Journal of Computer Mathematics},
volume = {89},
number = {5},
year = {2012},
ISSN = {00207160},
doi = {10.1080/00207160.2011.642300},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9716}
} 
