Noncontracting grammar

In formal language theory, a noncontracting grammar (also called monotonic grammar) is a type of formal grammar whose production rules never decrease the total length of a string during derivation. This means that when applying any rule to transform one string into another, the resulting string must have at least as many symbols as the original.

Noncontracting grammars are significant because they are equivalent in expressive power to context-sensitive grammars and define the same class of languages (the context-sensitive languages) in the Chomsky hierarchy. This equivalence makes them important for understanding the computational limits of natural language processing and compiler design, as they can model complex linguistic phenomena while maintaining certain desirable mathematical properties. Some authors use the term context-sensitive grammar to refer to noncontracting grammars in general, though this usage varies in the literature.

A closely related concept is the essentially noncontracting grammar, which allows one special exception: a rule that produces the empty string from the start symbol, provided that the start symbol never appears elsewhere in the grammar.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.