Is there a s-grammar for $L_2=\{a^nb^m, n > m \ge 0\}$?

219 Views Asked by At

Peter Linz - An introduction to formal languages and automata (2001) third edition:

A context free grammar $G=(V,T,S,P)$ is said to be a simple grammar or s-grammar if all its productions are of the form

$A \rightarrow aX$

where $A \in V, a \in T, x \in V^*$ , and any pair $(A,a)$ occurs at most once in $P$.

Define a simple grammar or s-grammar for $L_1=\{a^nb^n, n \ge 1\}$ is not difficult.

$S \rightarrow aY$

$Y \rightarrow aYB | b$

$B \rightarrow b$

How about this Language: $L_2=\{a^nb^m, n > m \ge 0\}$ . Is there a s-grammar for this language?