I would like to get some help for finding the context-sensitive grammar for the language:

$$L_1=\{a^ib^jc^{ij} \mid i,j\geq 0\}.$$

To answer the question before it's written here, yes I've tried to construct it myself, but my attempts are far from promising, so I don't include them, because there is no point (also I've tried to find a similar question - without luck).

Additionally, although I'm familiar with the one question per post rule, I'm adding another language here:

$$L_2=\{a^ib^jc^{i^j} \mid i,j\geq 0\}.$$

(The reason is that I think these two have a similar solution — of course if I'm mistaken, I will erase it.)

Please include the thought process as I've just started learning grammars. Any hint appreciated.


1 Answer 1


Designing context-sensitive grammars (with productions $\alpha X \gamma \to \alpha \beta \gamma$ with $\beta \neq \varepsilon$) is no fun at all. It is slightly more convenient to construct monotone grammars (with productions $\alpha \to \beta$ with $|\alpha| \le |\beta|$). There is a standard construction from one to the other.

But even then it is full of tiny details that have to be observed.

It is relatively easy to construct a grammar for $\{ La^ib^jc^{ij} \mid i,j\ge 0 \}$. First generate strings of the form $LB^jA^i$, just like in a context-free grammar. Add the rule $BA \to ABC$, so that if every $A$ moves over every $B$ we generate $ij$ $C$'s. But now we have $C$'s in between. Let $B$'s move over $C$'s whenever needed.

Then we have to rewrite $A,B,C$ into $a,b,c$ respectively provided they are in the right order. This can be done using the boundary symbol $L$ and the productions $LA \to La$, $aA \to aa$, $aB\to ab$ etcetera. Like a finite state automaton that accepts $a^*b^*c^*$.

Now what about the $L$? We used it to mark the start of the string. According to the rules of monotone grammars it cannot be deleted. Well, let the $L$ double as one of the $a$'s. But then we should carefully match the $c$;s with the new design. Thus start by generating the context-free language $aB^jA^iC^j$.

Done? not yet. We now always have at least one $a$, i.e., $i>0$. Add these special cases.

Problem with the construction is its correctness. Productions can be applied in any order, not only the one order you have considered during its construction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.