Book chapterMEDUNA Alexander and ZEMEK Petr. OneSided Random Context Grammars with Leftmost Derivations. LNCS Festschrift Series: Languages Alive  Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday. BerlinHeidelberg: Springer Verlag, 2012, pp. 160173. ISBN 9783642316432. Available from: https://www.scopus.com/record/display.uri?eid=2s2.084867018824&origin=resultslist  Publication language:  english 

Original title:  OneSided Random Context Grammars with Leftmost Derivations 

Title (cs):  Jednostranné gramatiky s nahodilým kontextem s levými derivacemi 

Pages:  160173 

Book:  LNCS Festschrift Series: Languages Alive  Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday 

Place:  BerlinHeidelberg, DE 

Year:  2012 

URL:  https://www.scopus.com/record/display.uri?eid=2s2.084867018824&origin=resultslist 

ISBN:  9783642316432 

Publisher:  Springer Verlag 

Keywords 

formal languages, regulated rewriting, onesided random context grammars, leftmost derivations, generative power 
Annotation 

In this paper, we study the generative power of onesided random context grammars working in a leftmost way. More specifically, by analogy with the three wellknown types of leftmost derivations in regulated grammars, we introduce three types of leftmost derivations to onesided random context grammars and prove the following three results. (I) Onesided random context grammars with type1 leftmost derivations characterize the family of contextfree languages. (II) Onesided random context grammars with type2 and type3 leftmost derivations characterize the family of recursively enumerable languages. (III) Propagating onesided random context grammars with type2 and type3 leftmost derivations characterize the family of contextsensitive languages. In the conclusion, the generative power of random context grammars and onesided random context grammars with leftmost derivations is compared.

BibTeX: 

@INBOOK{
author = {Alexander Meduna and Petr Zemek},
title = {OneSided Random Context Grammars with Leftmost Derivations},
pages = {160173},
booktitle = {LNCS Festschrift Series: Languages Alive  Essays Dedicated
to J{\"{u}}rgen Dassow on the Occasion of His 65th
Birthday},
year = {2012},
location = {BerlinHeidelberg, DE},
publisher = {Springer Verlag},
ISBN = {9783642316432},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9717}
} 
