Noncontracting grammar
In formal language theory, a grammar is noncontracting (or monotonic) if for all of its production rules, α → β (where α and β are strings of nonterminal and terminal symbols), it holds that |α| ≤ |β|, that is β has at least as many symbols as α. A grammar is essentially noncontracting if there may be one exception, namely, a rule S → ε where S is the start symbol and ε the empty string, and furthermore, S never occurs in the right-hand side of any rule.
A context-sensitive grammar is a noncontracting grammar in which all rules are of the form αAβ → αγβ, where A is a nonterminal, and γ is a nonempty string of nonterminal and/or terminal symbols.
However, some authors use the term context-sensitive grammar to refer to noncontracting grammars in general.[1]
A noncontracting grammar in which |α| < |β| for all rules is called a growing context-sensitive grammar.
History
Chomsky (1959) introduced the Chomsky hierarchy, in which context-sensitive grammars occur as "type 1" grammars; general noncontracting grammars do not occur.[2]
Chomsky (1963) calls a noncontracting grammar a "type 1 grammar", and a context-sensitive grammar a "type 2 grammar", and by presenting a conversion from the former into the latter, proves the two weakly equivalent .[3]
Kuroda (1964) introduced Kuroda normal form, into which all noncontracting grammars can be converted.[4]
Example
| S | → | abc |
| S | → | aSBc |
| cB | → | Bc |
| bB | → | bb |
This grammar, with the start symbol S, generates the language { anbncn : n ≥ 1 },[5] which is not context-free due to the pumping lemma.
A context-sensitive grammar for the same language is shown below.
Expressive power
Every context-sensitive grammar is a noncontracting grammar.
There are easy procedures for
- bringing any noncontracting grammar into Kuroda normal form,[4][6] and
- converting any noncontracting grammar in Kuroda normal form into a context-sensitive grammar.
Hence, these three types of grammar are equal in expressive power, all describing exactly the context-sensitive languages that do not include the empty string; the essentially noncontracting grammars describe exactly the set of context-sensitive languages.
A direct conversion
A direct conversion into context-sensitive grammars, avoiding Kuroda normal form:
For an arbitrary noncontracting grammar (N, Σ, P, S), construct the context-sensitive grammar (N’, Σ, P’, S) as follows:
- For every terminal symbol a ∈ Σ, introduce a new nonterminal symbol [a] ∈ N’, and a new rule ([a] → a) ∈ P’.
- In the rules of P, replace every terminal symbol a by its corresponding nonterminal symbol [a]. As a result, all these rules are of the form X1...Xm → Y1...Yn for nonterminals Xi, Yj and m≤n.
- Replace each rule X1...Xm → Y1...Yn with m>1 by 2m rules:[note 1]
X1 X2 ... Xm-1 Xm → Z1 X2 ... Xm-1 Xm Z1 X2 ... Xm-1 Xm → Z1 Z2 ... Xm-1 Xm : Z1 Z2 ... Xm-1 Xm → Z1 Z2 ... Zm-1 Xm Z1 Z2 ... Zm-1 Xm → Z1 Z2 ... Zm-1 Zm Ym+1 ... Yn Z1 Z2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Z2 ... Zm-1 Zm Ym+1 ... Yn Y1 Z2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Y2 ... Zm-1 Zm Ym+1 ... Yn : Y1 Y2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Y2 ... Ym-1 Zm Ym+1 ... Yn Y1 Y2 ... Ym-1 Zm Ym+1 ... Yn → Y1 Y2 ... Ym-1 Ym Ym+1 ... Yn
For example, the above noncontracting grammar for { anbncn | n ≥ 1 } leads to the following context-sensitive grammar (with start symbol S) for the same language:
| [a] | → | a | from step 1 | ||||
| [b] | → | b | from step 1 | ||||
| [c] | → | c | from step 1 | ||||
| S | → | [a] | [b] | [c] | from step 2, unchanged | ||
| S | → | [a] | S | B | [c] | from step 2, unchanged | |
| from step 2, further modified below | |||||||
| [c] | B | → | Z1 | B | modified from above in step 3 | ||
| Z1 | B | → | Z1 | Z2 | modified from above in step 3 | ||
| Z1 | Z2 | → | B | Z2 | modified from above in step 3 | ||
| B | Z2 | → | B | [c] | modified from above in step 3 | ||
| from step 2, further modified below | |||||||
| [b] | B | → | Z3 | B | modified from above in step 3 | ||
| Z3 | B | → | Z3 | Z4 | modified from above in step 3 | ||
| Z3 | Z4 | → | [b] | Z4 | modified from above in step 3 | ||
| [b] | Z4 | → | [b] | [b] | modified from above in step 3 |
See also
Notes
<templatestyles src="Reflist/styles.css" />
- ↑ For convenience, the non-context part of left and right hand side is shown in boldface.
Script error: No such module "Check for unknown parameters".
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1".
- ↑ Chomsky, N. 1959a. On certain formal properties of grammars. Information and Control 2: 137–67. (141–42 for the definitions)
- ↑ Script error: No such module "citation/CS1". Here: pp. 360–363 and 367
- ↑ a b Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Footnotes"., Example 2.1, p. 188
- ↑ Script error: No such module "Footnotes"., Theorem 2.2, p. 190
- ↑ Script error: No such module "Footnotes"., Theorem 2.1, p. 187
- ↑ Script error: No such module "citation/CS1". Exercise 9.9, p.230. In the 2003 edition, the chapter on noncontracting / context-sensitive languages has been omitted.
Script error: No such module "Check for unknown parameters".
- Script error: No such module "Citation/CS1".
- Script error: No such module "citation/CS1".
Script error: No such module "Navbox".