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.
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 $$