Detail publikace

A Two-Way PC Grammar Systems Based on Regular Grammars

KALÁB, P.

Originální název

A Two-Way PC Grammar Systems Based on Regular Grammars

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

KALÁB, P.

Vydáno

29. 4. 2004

Nakladatel

Faculty of Information Technology BUT

Místo

Brno

ISBN

80-214-2635-7

Kniha

Proceedings of 10th Conference and Competition STUDENT EEICT 2004

Edice

Volume 2

Strany od

252

Strany do

256

Strany počet

5

BibTex

@inproceedings{BUT16935,
  author="Petr {Kaláb}",
  title="A Two-Way PC Grammar Systems Based on Regular Grammars",
  booktitle="Proceedings of 10th Conference and Competition STUDENT EEICT 2004",
  year="2004",
  series="Volume 2",
  pages="252--256",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  isbn="80-214-2635-7"
}