# How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

I have been trying to understand how the language $$L = \{a^m b^n c^p d^q \mid m*n=p+q\}$$) is context-sensitive?

I first encountered this question here.

Would be grateful if you could provide some intuition for identifying class of such language.

Thank you!

• Why would $\varepsilon$ not be valid in a CSL? A context-sensitive grammar is always allowed to have a rule $S\to \varepsilon$, with $S$ the start symbol. Aug 23 at 17:23
• @Nathaniel, yes, you are right! (edited) Still not sure how this language is CSL tho, any idea?
– yash
Aug 25 at 2:16

I think the language is indeed context-sensitive. Here is a non-contracting grammar generating it.

$$S \to A' \mid B' \mid aS' \mid \varepsilon$$

$$A' \to aA' \mid a$$ (in the case there is no $$b$$'s, then the word is $$a^m$$)

$$B' \to bB' \mid b$$ (in the case there is no $$a$$'s, then the word is $$b^n$$)

$$S' \to S'A \mid BS'X\mid BX$$

$$BA\to ABX$$

$$XA \to AX$$

$$XB \to BX$$

$$aA \to aa$$

$$aB\to ab$$

$$bB \to bb$$

$$bX\to bc \mid bd$$

$$cX \to cc \mid cd$$

$$dX \to dd$$

The idea is the following:

• First, we distinguish the cases of the empty word, a word with no $$b$$'s and a word with no $$a$$'s. These cases can be treated with simple rules.
• In the other cases, the word is $$a^mb^nc^pd^q$$ with $$m>0$$, $$n>0$$ and $$p+q>0$$ :
• we first generate a word like $$aB^nA^{m-1}X^n$$;
• we switch the positions of $$B$$'s and $$A$$'s. Each time a swap is done, we create a letter $$X$$. Since there are $$(m-1)\times n$$ total swaps, there will be $$m\times n$$ letters $$X$$;
• then, using the starting $$a$$, we replace all variables with terminals. If there is still a $$B$$ to the left of an $$A$$, then the $$A$$ will never be transformed into a terminal (this insures that the grammar cannot generate words that are not in the language). The idea is the same with $$A$$'s or $$B$$'s to the left of an $$X$$.

There may be some mistakes in the grammar, but I think the general idea works.