Noncontracting grammar

Noncontracting grammar

Contents

Formal definition

In formal language theory, a grammar is noncontracting (or monotonic) if all of its production rules are of the form

α → β where |α| ≤ |β|, where |α| denotes the length of α.

That is, none of the rules decreases the size of the string that is being rewritten.

It is essentially noncontracting if there may be one exception, namely, a rule

S → ε

where S is the start symbol and ε the empty string.

Example

S → abc
S → aSBc
cB → Bc
bB → bb

This grammar generates the language  \{ a^n b^n c^n : n \ge 1 \} , which is not context-free.

There is also a (much more complex) noncontracting grammar for the language  \{ a^n b^n c^n d^n : n \ge 1 \} .

Equivalent types of grammars; expressive power

There is an easy procedure for bringing any noncontracting grammar into Kuroda normal form.

Procedures are known for transforming any noncontracting grammar into a context-sensitive grammar and vice versa.

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 languages that do not include the empty string, while the essentially noncontracting grammars describe exactly the set of context-sensitive languages.

See also


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • 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… …   Wikipedia

  • Context-sensitive language — In theoretical computer science, a context sensitive language is a formal language that can be defined by a context sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”