Publication Details

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

TECHET Jiří. A Note on Scattered Context Grammars with Non-Context-Free Components. In: MEMICS 2007 Proceedings. Znojmo: Ing. Zdeněk Novotný, CSc., 2007, pp. 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. (DIFS FIT BUT)
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
Conference
MEMICS'07 -- 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Znojmo, CZ
ISBN
978-80-7355-077-6
Publisher
Ing. Zdeněk Novotný, CSc.
Place
Znojmo, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8460,
   author = "Ji\v{r}\'{i} Techet",
   title = "A Note on Scattered Context Grammars with Non-Context-Free Components",
   pages = "225--232",
   booktitle = "MEMICS 2007 Proceedings",
   year = 2007,
   location = "Znojmo, CZ",
   publisher = "Ing. Zden\v{e}k Novotn\'{y}, CSc.",
   ISBN = "978-80-7355-077-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8460"
}
Back to top