Publication Details

Two-way PC Grammar Systems Based on Regular Grammars

KALÁB, P. Two-way PC Grammar Systems Based on Regular Grammars. Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modeling. 1st edition. Ostrava: 2004. p. 111-118. ISBN: 80-85988-99-2.
Czech title
Dvousměrné PC gramatické systémy složené z regulárních gramatik
Type
conference paper
Language
English
Authors
Kaláb Petr, Ing.
Keywords

Context-free grammar, left-linear grammar, right-linear grammar, grammar system, communication step, two-way PC grammar systems, derivation, production, sentential form, nonterminal, terminal

Abstract

Besides derivation and communication steps, a two-way PC grammar system can make a reduction step during which it reduces the right-hand side of a context-free production to its left hand-side. This paper proves that every non-unary recursively enumerable language is defined by a centralized two-way grammar system, Γ, with three components in a very economical way. Indeed, Γ's master has only three nonterminals and one communication production; furthermore, it produces all sentential forms with no more than two occurrences of nonterminals. In addition, during every computation, Γ makes a single communication step. Some variants of two-way PC grammar system are discussed in the conclusion of this paper.

Published
2004
Pages
111–118
Proceedings
Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modeling
Series
1st edition
ISBN
80-85988-99-2
Place
Ostrava
BibTeX 
@inproceedings{BUT16915,
  author="Petr {Kaláb}",
  title="Two-way PC Grammar Systems Based on Regular Grammars",
  booktitle="Proceedings of 7th International Conference ISIM'04  Information Systems Implementation and Modeling",
  year="2004",
  series="1st edition",
  pages="111--118",
  address="Ostrava",
  isbn="80-85988-99-2"
}
Back to top