J 2012

On restricted context-free grammars

DASSOW, Jürgen a Tomáš MASOPUST

Základní údaje

Originální název

On restricted context-free grammars

Autoři

DASSOW, Jürgen a Tomáš MASOPUST

Vydání

Journal of Computer and System Sciences, Elsevier, 2012, 0022-0000

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Impakt faktor

Impact factor: 1.000

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

Klíčová slova česky

Context-free grammars; Derivation restriction; Normal forms; Generative power

Klíčová slova anglicky

Context-free grammars; Derivation restriction; Normal forms; Generative power

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 26. 1. 2012 08:59, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

V originále

Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols.