Publication Details

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

MEDUNA Alexander and RYCHNOVSKÝ Lukáš. Infinite Language Hierarchy Based on Regular-Regulated Right-Linear Grammars with Start Strings. Philippine Computing Journal, vol. 2008, no. 3, pp. 1-5. ISSN 1908-1995.
English title
Philippine Computing Journal
Type
journal article
Language
czech
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Rychnovský Lukáš, Ing. (DIFS FIT BUT)
URL
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, PH
BibTeX 
@ARTICLE{FITPUB9004,
   author = "Alexander Meduna and Luk\'{a}\v{s} Rychnovsk\'{y}",
   title = "Infinite Language Hierarchy Based on Regular-Regulated Right-Linear Grammars with Start Strings",
   pages = "1--5",
   booktitle = "Philippine Computing Journal",
   journal = "Philippine Computing Journal",
   volume = 2008,
   number = 3,
   year = 2008,
   location = "Manila, PH",
   ISSN = "1908-1995",
   language = "czech",
   url = "https://www.fit.vut.cz/research/publication/9004"
}
Back to top