Monotone Grammar

languages

Definition

Monotone Grammar

A grammar is called monotone if every production rule in $P$ is context-sensitive.

Equivalently, every production rule $\alpha \to \beta$ satisfies

$$|\alpha |\le |\beta |(\alpha \ne \epsilon )$$

If the start symbol $S$ does not appear on the right-hand side of any production, then the rule

$$S\to \epsilon$$

is also allowed.

Examples

Grammar for $\{a^n{b}^n{c}^n\mid n\ge 0\}$

Consider the context-sensitive grammar

$$G=(\{S,T,C\},\{a,b,c\},P,S)$$

where $P$ contains the following production rules:

$$\begin{array}{rl}S& \to \epsilon \mid abc\mid aTbc\\ T& \to aTbC\mid abC\\ Cb& \to bC\\ Cc& \to cc\end{array}$$

Then

$$L(G)=\{a^n{b}^n{c}^n\mid n\ge 0\}.$$