# Language of context-sensitive grammar

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 \}$$

• 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". – Steven May 5 at 18:03
• 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 – GuardGoose May 5 at 18:09

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$$.
• So the notation would looking something akin to this: L = (a^2n+2, b^n+1a^n | n > 1)`? – GuardGoose May 5 at 18:26