Detail publikace

One-Sided Random Context Grammars with Leftmost Derivations

Originální název

One-Sided Random Context Grammars with Leftmost Derivations

Anglický název

One-Sided Random Context Grammars with Leftmost Derivations

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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{BUT96922,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars with Leftmost Derivations",
  annote="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.",
  address="Springer Verlag",
  booktitle="LNCS Festschrift Series: Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday",
  chapter="96922",
  doi="10.1007/978-3-642-31644-9_11",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Springer Verlag",
  year="2012",
  month="july",
  pages="160--173",
  publisher="Springer Verlag",
  type="book chapter"
}