I have the following context-sensitive grammar:

$$ \begin{align*} &S \to xSy \mid a \mid b \\ &Xa \to aa \\ &Xb \to bb \\ &Y \to a \end{align*} $$

I know what it does, as it always ends in $a$ and is preceded by 3 $a$s or 3 $b$s. I'm just not sure how to write this in set notation and would appreciate any help. Would it be something like this? $$ L = \{a^n,b^m \mid n \ge 1, 0 < m \le 3 \} $$

  • $\begingroup$ Your intuition is wrong, for example all of "a", "b", and "bba" are in the language but do no start with three "a"s or three "b"s. Also "b" is in the language but does not end with "a". $\endgroup$
    – Steven
    Commented May 5, 2020 at 18:03
  • $\begingroup$ okay, so I gather that my attempted set notation is wrong, and thank you I didn't realise it could just be "a" and "b" as well and doesn't need to end in "a", so it could be something like this `L = {a^n, b^n | 0 < n <= 3} @Steven $\endgroup$
    – GuardGoose
    Commented May 5, 2020 at 18:09

1 Answer 1


There are basically two possible types of derivations:

  1. Ones that start $S \to^* X^naY^n$.
  2. Ones that start $S \to^* X^nbY^n$.

Derivations of the first type will produce $a^{2n+1}$, those of the second type will produce $b^{n+1} a^n$.

  • $\begingroup$ So the notation would looking something akin to this: L = (a^2n+2, b^n+1a^n | n > 1)? $\endgroup$
    – GuardGoose
    Commented May 5, 2020 at 18:26
  • $\begingroup$ Right, something of this sort (but with a few small corrections, that I'll let you work out on your own). $\endgroup$ Commented May 5, 2020 at 18:26

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.