Book chapter

MEDUNA Alexander and ZEMEK Petr. One-Sided Random Context Grammars with Leftmost Derivations. LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday. Berlin-Heidelberg: Springer Verlag, 2012, pp. 160-173. ISBN 978-3-642-31643-2. Available from: https://www.scopus.com/record/display.uri?eid=2-s2.0-84867018824&origin=resultslist
Publication language:english
Original title:One-Sided Random Context Grammars with Leftmost Derivations
Title (cs):Jednostranné gramatiky s nahodilým kontextem s levými derivacemi
Pages:160-173
Book:LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday
Place:Berlin-Heidelberg, DE
Year:2012
URL:https://www.scopus.com/record/display.uri?eid=2-s2.0-84867018824&origin=resultslist
ISBN:978-3-642-31643-2
Publisher:Springer Verlag
Keywords
formal languages, regulated rewriting, one-sided random context grammars, leftmost derivations, generative power
Annotation
In this paper, we study the generative power of one-sided random context grammars working in a leftmost way. More specifically, by analogy with the three well-known types of leftmost derivations in regulated grammars, we introduce three types of leftmost derivations to one-sided random context grammars and prove the following three results. (I) One-sided random context grammars with type-1 leftmost derivations characterize the family of context-free languages. (II) One-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of recursively enumerable languages. (III) Propagating one-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of context-sensitive languages. In the conclusion, the generative power of random context grammars and one-sided random context grammars with leftmost derivations is compared.
BibTeX:
@INBOOK{
   author = {Alexander Meduna and Petr Zemek},
   title = {One-Sided Random Context Grammars with Leftmost Derivations},
   pages = {160--173},
   booktitle = {LNCS Festschrift Series: Languages Alive - Essays Dedicated
	to J{\"{u}}rgen Dassow on the Occasion of His 65th
	Birthday},
   year = {2012},
   location = {Berlin-Heidelberg, DE},
   publisher = {Springer Verlag},
   ISBN = {978-3-642-31643-2},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9717}
}

Your IPv4 address: 54.158.55.5
Switch to IPv6 connection

DNSSEC [dnssec]