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. A noncontracting grammar in which |α| < |β| for all rules is called a growing context-sensitive grammar. Chomsky (1959) introduced the Chomsky hierarchy, in which context-sensitive grammars occur as "type 1" grammars; general noncontracting grammars do not occur. 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 . Kuroda (1964) introduced Kuroda normal form, into which all noncontracting grammars can be converted. This grammar, with the start symbol S, generates the language { anbncn : n ≥ 1 } , which is not context-free due to the pumping lemma. A context-sensitive grammar for the same language is shown below. Every context-sensitive grammar is a noncontracting grammar. There are easy procedures for bringing any noncontracting grammar into Kuroda normal form, 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.