Terminating left-hand sides of scattered context productions M. Nivat (Q1566740)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Terminating left-hand sides of scattered context productions M. Nivat |
scientific article |
Statements
Terminating left-hand sides of scattered context productions M. Nivat (English)
0 references
4 June 2000
0 references
The left-hand side of a scattered context production, \((A_{1},A_{2},\ldots,A_{n})\rightarrow (x_{1},x_{2},\ldots,x_{n})\), is terminating if \(A_{1}A_{2}\ldots A_{n}\) derives a terminal word. This paper discusses scattered context grammars whose sentential forms contain sequences of nonterminals formed by shuffling the terminating left-hand sides of productions. It proves that these grammars do not generate some context-sensitive languages, so they are less powerful than the scattered context grammars whose sentential forms are unrestricted. In its conclusion, this paper demonstrates the impact of this result and discusses open problems.
0 references
scattered context grammars
0 references
generative power
0 references
0 references