I have been trying to find a context sensitive grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$ for some time but I cannot get it done. Any ideas ?


In the following grammar the first block of productions ensures that the right amount of $a,b,c$, and $d$ is generated, in some order. The terminal $a$ is represented by the nonterminal $A$, $b$ by $B$, etc. They also ensure that $X$, which represents a $a$, is at the end of the sentential form.

The next block ensures that $A,B,C,D$ can be reordered.

The last block ensures that terminals are generated from right to left in the correct order (first $d$, then $c$, then $b$, and finally $a$).

$$ \begin{align*} S &\to ABBCCCDS'X \\ S' &\to AABBCCCDS' \mid BDDD\\ \\ BA & \to AB \\ CA & \to AC \\ CB & \to BC \\ DA & \to AD \\ DB & \to BD \\ DC & \to CD \\ \\ DX &\to Xd \\ X &\to Y \\ CY &\to Yc \\ Y &\to W \\ BW &\to Wb \\ W &\to Z \\ AZ &\to Za \\ Z & \to a \end{align*} $$

  • $\begingroup$ my automata rejected this, does not seem to be correct because of order probably EDIT: order is a b c d from left to right, but it seems to be getting correctly that part $\endgroup$ – unknownUsername39493 Apr 15 '20 at 13:19
  • $\begingroup$ Can you provide a sentence that is in the language but is not generated by the grammar, or a derivation of a sentence that is not in the language? Also there was a spurious $S$ in right part the second production. I removed it. $\endgroup$ – Steven Apr 15 '20 at 13:22
  • $\begingroup$ Thanks, it works with that spurious S removed. Thank you some much for your time. $\endgroup$ – unknownUsername39493 Apr 15 '20 at 13:53

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.