A variant of random context grammars: Semi-conditional grammars (Q1072714): Difference between revisions
From MaRDI portal
Latest revision as of 13:17, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A variant of random context grammars: Semi-conditional grammars |
scientific article |
Statements
A variant of random context grammars: Semi-conditional grammars (English)
0 references
1985
0 references
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.
0 references
regulated derivations
0 references
Chomsky hierarchy
0 references
inclusions between families of languages
0 references
context-free semi-conditional grammars
0 references
context-sensitive languages
0 references
generative power
0 references