Publication Details

A Two-Way PC Grammar Systems Based on Regular Grammars

KALÁB Petr. A Two-Way PC Grammar Systems Based on Regular Grammars. In: Proceedings of 10th Conference and Competition STUDENT EEICT 2004. Volume 2. Brno: Faculty of Information Technology BUT, 2004, pp. 252-256. ISBN 80-214-2635-7.
Czech title
Dvousměrné PC gramatické systémy založené na regulárních gramatikách
Type
conference paper
Language
english
Authors
Kaláb Petr, Ing. (DIFS FIT BUT)
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
252-256
Proceedings
Proceedings of 10th Conference and Competition STUDENT EEICT 2004
Series
Volume 2
Conference
Student EEICT 2004, Brno, CZ
ISBN
80-214-2635-7
Publisher
Faculty of Information Technology BUT
Place
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7445,
   author = "Petr Kal\'{a}b",
   title = "A Two-Way PC Grammar Systems Based on Regular Grammars",
   pages = "252--256",
   booktitle = "Proceedings of 10th Conference and Competition STUDENT EEICT 2004",
   series = "Volume 2",
   year = 2004,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-2635-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7445"
}
Back to top