Publication detail

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

TECHET, J.

Original Title

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

Type

conference paper

Language

English

Original 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.

Keywords

formal languages, scattered context grammars, generative power

Authors

TECHET, J.

RIV year

2007

Released

26. 10. 2007

Publisher

Ing. Zdeněk Novotný, CSc.

Location

Znojmo

ISBN

978-80-7355-077-6

Book

MEMICS 2007 Proceedings

Pages from

225

Pages to

232

Pages count

8

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"
}