Publication Details

One-Sided Random Context Grammars with Leftmost Derivations

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
Czech title
Jednostranné gramatiky s nahodilým kontextem s levými derivacemi
Type
book chapter
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Zemek Petr, Ing. (DIFS FIT BUT)
URL
Keywords

formal languages, regulated rewriting, one-sided random context grammars, leftmost derivations, generative power

Abstract

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.

Published
2012
Pages
160-173
Book
LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday
ISBN
978-3-642-31643-2
Publisher
Springer Verlag
Place
Berlin-Heidelberg, DE
DOI
10.1007/978-3-642-31644-9_11
EID Scopus
2-s2.0-84867018824
BibTeX 
@INBOOK{FITPUB9717,
   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",
   doi = "10.1007/978-3-642-31644-9\_11",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9717"
}
Back to top