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 May 5 '20 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 May 5 '20 at 18:09

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 May 5 '20 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$ – Yuval Filmus May 5 '20 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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