Monotonous grammar
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)