A variant of random context grammars: Semi-conditional grammars
type: Item
instance of: scholarly article
title: A variant of random context grammars: Semi-conditional grammars
zbMATH Open document ID: 0587.68071
DOI: 10.1016/0304-3975(85)90056-8
author: Gheorghe Păun
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: The notion of semi-conditional grammar is introduced. With each rule in the semi-conditional grammar a pair of strings, say \(w_ 1\) and \(w_ 2\), is associated. A rule can be applied to a sentential form w only if \(w_ 1\) is a substring of w and \(w_ 2\) is not contained in it. The paper concentrates mainly to hierarchical properties of families of languages generated by context-free semi-conditional grammars in dependence of the lengths of the \(w_ 1\) and \(w_ 2\) parts of rules. It is proved, that such grammars with very short conditioning parts of rules can generate the whole family of context-sensitive languages. The role of additional regularing mechanisms applied to the case of semi-conditional grammars is studied in connection with the question of generative power of grammars. In the closing section of the article, some interesting open problems are formulated.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3943056
zbMATH Keywords: regulated derivations
zbMATH Keywords: Chomsky hierarchy
zbMATH Keywords: inclusions between families of languages
zbMATH Keywords: context-free semi-conditional grammars
zbMATH Keywords: context-sensitive languages
zbMATH Keywords: generative power
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90056-8
OpenAlex ID: W2107399756
cites work: A note on leftmost restricted random context grammars
cites work: Q3725562
cites work: Grammars with partial ordering of the rules
cites work: Q3690243
cites work: Some restrictive devices for context-free grammars
cites work: On the generative capacity of conditional grammars
cites work: On the generative capacity of tree controlled grammars
cites work: Programmed Grammars and Classes of Formal Languages
cites work: Q5678435
cites work: Q5626298
description: scientific article; zbMATH DE number 3943056