On restricted context-free grammars

DASSOW, Jürgen a Tomáš MASOPUST. On restricted context-free grammars. In DLT 2010, LNCS 6224. London, ON, Canada: Springer-Verlag Berlin Heidelberg, 2010, s. 434-435. ISBN 978-3-642-14454-7.

Základní údaje

Originální název

On restricted context-free grammars

Autoři

DASSOW, Jürgen a Tomáš MASOPUST

Vydání

London, ON, Canada, DLT 2010, LNCS 6224, od s. 434-435, 2010

Nakladatel

Springer-Verlag Berlin Heidelberg

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

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

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-14454-7

ISSN

UT WoS

000286402700040

Klíčová slova anglicky

Regulated rewriting, context-free rules, generative power.

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

In context-free grammars, each derivation step can be characterized so that (i) a nonterminal of the current sentential form is chosen and (ii) rewritten by a rule. However, it is well-known that context-free grammars are not able to cover all aspects of natural languages and/or programming languages. Therefore, there were defined many grammars with context-free rules and some mechanism controlling the application of rules, e. g., in random context grammars and their variants, a rule is only applicable if the current sentential form contains some letters or subwords and some letters or words do not occur in it. Therefore, in grammars controlled by context, each derivation step can be characterized so that (i) subsets of applicable nonterminals and rules are determined according to the symbols appearing in the current sentential form, (ii) an applicable nonterminal is chosen and (iii) rewritten by an applicable rule.