formal language theory In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

, a

grammar In linguistics, the grammar of a natural language is its set of structure, structural constraints on speakers' or writers' composition of clause (linguistics), clauses, phrases, and words. The term can also refer to the study of such constraint ...

is noncontracting (or monotonic) if all of its production rules are of the form α → β where α and β are

strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...

nonterminal In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ...

and terminal symbols, and the length of α is less than or equal to that of β, , α, ≤ , β, , that is β is not shorter than α. 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. None of the rules of a noncontracting grammar decreases the length of the string that is being rewritten. If each rule even properly increases the length, the grammar is called a growing context-sensitive grammar.

History

Chomsky (1963) called a noncontracting grammar a type 1 grammar; in the same work, he called a

context-sensitive grammar A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than co ...

a "type 2 grammar", and he proved that these two are weakly equivalent (context-free grammars were designated "type 4" in this work). The type numbering scheme in this 1963 work of Chomsky does not coincide with the earlier one known today as the

Chomsky hierarchy In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by ...

because he was trying to emphasize the distinction between weak enerativeand strong tructuralequivalence; in his 1959 work he had used "type 1 grammar" to denote a context-sensitive grammar and "type 2" for context-free.Chomsky, N. 1959a. On certain formal properties of grammars. Information and Control 2: 137–67. (141–42 for the definitions)

Example

This grammar, with the start symbol ''S'', generates the language , which is not context-free due to the

pumping lemma In the theory of formal languages, the pumping lemma may refer to: *Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to pro ...

. A context-sensitive grammar for the same language is shown

below Below may refer to: *Earth *Ground (disambiguation) *Soil *Floor *Bottom (disambiguation) Bottom may refer to: Anatomy and sex * Bottom (BDSM), the partner in a BDSM who takes the passive, receiving, or obedient role, to that of the top or ...

Transforming into context-sensitive grammar

Every noncontracting grammar (''N'', Σ, ''P'', ''S'') can be transformed into a

(''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 → for nonterminals ''X''_''i'', ''Y''_''j'' and ''m''≤''n''. # Replace each rule → with ''m''>1 by 2''m'' rules:For convenience, the non-context part of left and right hand side is shown in boldface. :: ::where each ''Z''_''i'' ∈ ''N''’ is a new nonterminal not occurring elsewhere. For example, the above noncontracting grammar for leads to the following context-sensitive grammar (with start symbol ''S'') for the same language:

Expressive power

Similarly, there is an easy procedure for bringing any noncontracting grammar into

Kuroda normal form In formal language theory, a context-sensitive grammar is in Kuroda normal form if all production rules are of the form: :''AB'' → ''CD'' or :''A'' → ''BC'' or :''A'' → ''B'' or :''A'' → ''a'' where A, B, C and D are nonterminal symbols an ...

., Theorem 2.2, p. 190 Vice versa, every context-sensitive grammar and every Kuroda normal form grammar is trivially also a noncontracting grammar. Therefore, noncontracting grammars, grammars in Kuroda normal form, and context-sensitive grammars have the same expressive power. To be precise, the noncontracting grammars describe exactly the

context-sensitive language In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar). Context-sensitive is one of the four types of grammars in the Chomsky hierarc ...

s that do not include the empty string, while the essentially noncontracting grammars describe exactly the set of

Notes

References