Constructing phrase structure grammar of given language I am learning Formal Languages. I am stuck at a problem in which we have to construct a phrase structure grammar for the given language.
$L = \{a^ib^jc^id^j | i \geq 1, j \geq 1\}$
I came up with
$S \rightarrow aAcB$
$S \rightarrow AbBd$
$S \rightarrow abcd$
$A \rightarrow ab$
$B \rightarrow cd$
But these don't work for all strings. I think the problem I am facing is in controlling two separated letters. It would be very nice if I could get some insight into solving these and such similar problems. Thanks in advance.
 A: The first thing to check is if the language is context-free. With the pumping lemma it can be shown that $L=\{a^ib^jc^id^j\mid i,j\geq 1\}$ is not context-free (let $p$ be the pumping constant, and consider $a^pb^pc^pd^p$).
Hence we will need a context-sensitive grammar. First, let's add rules that generate the (context-free) language $L'=\{a^iC^iB^jd^j\mid i,j\geq 1\}$:
\begin{align}
S&\to XY\\
X&\to aC \\
X&\to aXC\\
Y&\to Bd\\
Y&\to BYd
\end{align}
So the kind of strings we can create with this are almost the same as the strings for $L$, except that we have variable letters $C$'s and $B$'s instead of terminals $c$'s and $b$'s, and their order should be swapped around. This is where we will use context-sensitivity. Note that the following rules allow us to replace $CB$ with $BC$:
\begin{align}
CB&\to CP\\
CP&\to QP\\
QP&\to QC\\
QC&\to BC
\end{align}
Finally we have to replace the $C's$ with $c's$ and the $B's$ with $b's$, but we must only allow this to happen if a $C$ has moved to the right of all the $B$'s, and vice versa. This is the case when a $C$ is next to a $d$, or when a $C$ is next to a $c$ that has already been replaced (and similar for the $B's$), thus we add the following rules to complete the grammar:
\begin{align}
Cd&\to cd\\
Cc&\to cc\\
aB&\to ab\\
bB&\to bb
\end{align}

An example of how this grammar generates the string $aabccd$:
$$
S\\
XY\\
aXCY\\
aaCCY\\
aaCCBd\\
aaCCPd\\
aaCQPd\\
aaCQCd\\
aaCBCd\\
aaCBcd\\
aaCPcd\\
aaQPcd\\
aaQCcd\\
aaBCcd\\
aabCcd\\
aabccd
$$
