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!

  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Aug 23 at 17:23
  • $\begingroup$ @Nathaniel, yes, you are right! (edited) Still not sure how this language is CSL tho, any idea? $\endgroup$
    – yash
    Aug 25 at 2:16

1 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.


Your Answer

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

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