# Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$

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.

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.