0
$\begingroup$

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!

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.