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

Question

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!

Answer 1

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.