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 ?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
3
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
