Publication Details

Infinite Language Hierarchy Based on Regular-Regulated Right-Linear Grammars with Start Strings

MEDUNA, A.; RYCHNOVSKÝ, L. Infinite Language Hierarchy Based on Regular-Regulated Right-Linear Grammars with Start Strings. Philippine Computing Journal, 2008, roč. 2008, č. 3, s. 1-5. ISSN: 1908-1995.

English title

Philippine Computing Journal

Type

journal article

Language

Czech

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Rychnovský Lukáš, Ing., Ph.D.

URL

http://www.philjol.info/index.php/PCJ

Keywords

right-linear grammars, regular regulation, infinite hierarchy of language families

Abstract

The present paper discusses regular-regulated right-linear grammars with start strings and their generative power under some additional restrictions.

Annotation

The present paper discusses regular-regulated right-linear
grammars with start strings rather than single symbols. It
demonstrates that these grammars with start strings consisting of no more than n + 1 symbols are stronger than these
grammars with start strings consisting of no more than n
symbols, for all n >= 1. On the other hand, these grammars
with start strings of any length only generate the family of
regular languages if they change the position of rewriting
finitely many times during the derivation of any sentence
from the generated language.

Published

2008

Pages

1–5

Journal

Philippine Computing Journal, vol. 2008, no. 3, ISSN 1908-1995

Book

Philippine Computing Journal

Place

Manila

BibTeX

@article{BUT49616,
  author="Alexandr {Meduna} and Lukáš {Rychnovský}",
  title="Infinite Language Hierarchy Based on Regular-Regulated Right-Linear Grammars with Start Strings",
  journal="Philippine Computing Journal",
  year="2008",
  volume="2008",
  number="3",
  pages="1--5",
  issn="1908-1995",
  url="http://www.philjol.info/index.php/PCJ"
}