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.

History

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.

Example

This grammar, with the start symbol ''S'', generates the language
,
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, 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 → 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. Exercise 9.9, p.230. In the 2003 edition, the chapter on noncontracting / context-sensitive languages has been omitted.

For example, the above noncontracting grammar for leads to the following context-sensitive grammar (with start symbol ''S'') for the same language:

See also

* Context-sensitive grammar
* Growing context-sensitive grammar
* Kuroda normal form

Notes

References

*
*

{{Formal languages and grammars, state=collapsed

Formal languages