On restricted context-free grammars
type: Item
instance of: scholarly article
title: On restricted context-free grammars
zbMATH Open document ID: 1247.68117
author: Tomáš Masopust
author: Jürgen Dassow
published in: Journal of Computer and System Sciences
publication date: 2012-05-11T00:00:00Z
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6033496
zbMATH Keywords: context-free grammars
zbMATH Keywords: derivation restriction
zbMATH Keywords: normal forms
zbMATH Keywords: generative power
MaRDI profile type: Publication
full work available at URL: j.jcss.2011.05.008
OpenAlex ID: W1999932874
cites work: Q5485990
cites work: A pumping lemma for random permitting context languages
cites work: A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
cites work: Simple restriction in context-free rewriting
cites work: On context-free rewriting with a simple restriction and its computational completeness
cites work: Some restrictive devices for context-free grammars
cites work: Grammars with Context Conditions and Their Applications
cites work: One-sided and two-sided context in formal grammars
cites work: A variant of random context grammars: Semi-conditional grammars
cites work: Q5626298
cites work: A shrinking lemma for random forbidding context languages
cites work: On Erasing Productions in Random Context Grammars
DOI: 10.1016/J.JCSS.2011.05.008
review text: The contribution investigates the generative power of several derivation-restricted context-free grammars. Many derivation restriction mechanisms for context-free grammars have already been studied in the literature, and the current contribution investigates a restriction on the non-terminals that allows/disallows the application of a production depending on the presence/absence of certain symbols in the sentential form. Context-free grammars using such restrictions on the derivations are shown to be equivalent in generative power to random context grammars [\textit{S. Ewert} and \textit{A. van der Walt}, ``The power and limitations of random context'', Top. Comput. Math. 9, 33--43 (2003; Zbl 1102.68619)]. While this equivalence is also true for the permitting variants (in which only the presence of symbols can be required), it remains an open question whether this is also true in the presence of forbidding context. With the equivalence established, the generative power for most classes is presented in some simple hierarchies.NEWLINENEWLINEThe equivalence is also used to derive new normal forms for random context grammars. It is even demonstrated that the obtained normal forms are as simple as possible (in a rather restricted sense). This is achieved by demonstrating that further restrictions to the context indeed limit the generative power. At last, the contribution investigates a minor twist on the previous model. Instead of non-terminals, productions can now force the presence/absence of terminal symbols in the sentential form. The main line of research is repeated for this model (with different arguments) to show that the non-erasing variant of this model characterizes exactly the context-sensitive languages. As before, the equivalence is used to derive a new normal form for this model.NEWLINENEWLINEThe contribution is expertly written and the main points can be understood on the first reading. However, it is very technical in the mathematical development. While…
description: scientific article; zbMATH DE number 6033496