Monotonous grammar

from Wikipedia, the free encyclopedia

A monotonous grammar (including non-shortening grammar , constrained grammar, or expansive grammar ) is a formal grammar that only contains production rules whose right side is not shorter than the left side. A derivation step in a monotonous grammar does not shorten the sentence form to be derived.

definition

Formally, a monotonous grammar is defined as 4-tuples with

  • a finite set V, called a vocabulary ( set of symbols ),
  • Terminal symbols ( alphabet ),
  • Non- terminal symbols ( metasymbols , variables ) 
  • Production rules to which the following applies:
    For each rule is , d. H. is no longer than .
  • a start symbol (also called a start variable ).

Some authors alternatively use the quadruple to identify a grammar .

If the exception rule is also allowed for monotonous grammars , provided there is no right-hand side of a rule, then the monotonous grammars generate exactly the context-sensitive languages and are therefore equivalent to the context-sensitive grammars .

example

The grammar with ,   ,    and :

creates the language .

literature

  • Carlos Martín Vide, Victor Mitrana, Gheorghe Păun (Eds.): Formal languages ​​and applications . ( Studies in Fuzziness and Soft Computing Vol. 148), Springer, Heidelberg et al. 2004, ISBN 3-540-20907-7 ( limited preview in the Google book search)