Publication Details

A Note on Scattered Context Grammars with Non-Context-Free Components

TECHET, J. A Note on Scattered Context Grammars with Non-Context-Free Components. In MEMICS 2007 Proceedings. Znojmo: Ing. Zdeněk Novotný, CSc., 2007. p. 225-232. ISBN: 978-80-7355-077-6.

Czech title

O gramatikách s rozptýleným kontextem s jinými než bezkontextovými komponentami

Type

conference paper

Language

English

Authors

Techet Jiří, Ing., Ph.D.

Keywords

formal languages, scattered context grammars, generative power

Abstract

Scattered context grammars, introduced as a straightforward generalization of context-free grammars, apply n context-free productions in parallel to generate their sentences. This paper discusses their restricted versions in which all components of scattered context productions are either linear or right-linear. We prove that the families of languages generated by these grammars are equivalent to the families generated by linear and right-linear simple matrix grammars. Finally, we mention the generative power of scattered context grammars with context-sensitive and unrestricted productions and discuss some open problems.

Published

2007

Pages

225–232

Proceedings

MEMICS 2007 Proceedings

ISBN

978-80-7355-077-6

Publisher

Ing. Zdeněk Novotný, CSc.

Place

Znojmo

BibTeX

@inproceedings{BUT25334,
  author="Jiří {Techet}",
  title="A Note on Scattered Context Grammars with Non-Context-Free Components",
  booktitle="MEMICS 2007 Proceedings",
  year="2007",
  pages="225--232",
  publisher="Ing. Zdeněk Novotný, CSc.",
  address="Znojmo",
  isbn="978-80-7355-077-6"
}