Return to Answer

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{align*} S & \rightarrow aSd \tag{1} \\ S & \rightarrow T \\ S & \rightarrow V \\ S & \rightarrow U \\ S & \rightarrow \epsilon \\ T & \rightarrow aTc \tag{2} \\ T & \rightarrow V \\ T & \rightarrow \epsilon \\ U & \rightarrow bUd \tag{3} \\ U & \rightarrow V \\ U & \rightarrow \epsilon \\ V & \rightarrow bVc \tag{4} \\ V & \rightarrow \epsilon \end{align*} Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{align*} S & \rightarrow aSd \tag{1} \\ S & \rightarrow T \\ S & \rightarrow V \\ S & \rightarrow U \\ S & \rightarrow \epsilon \\ T & \rightarrow aTc \tag{2} \\ T & \rightarrow V \\ T & \rightarrow \epsilon \\ U & \rightarrow bUd \tag{3} \\ U & \rightarrow V \\ U & \rightarrow \epsilon \\ V & \rightarrow bVc \tag{4} \\ V & \rightarrow \epsilon \end{align*} Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

A word $w = a^nb^mc^pd^q \in{} L$ can be constructed as follows:

1. Apply the rule (1) $\min(m, q) =: l$ times. You get $$\underbrace{a\ldots{}a}_{l}S\underbrace{d\ldots{}d}_l$$.

2. If $m \geq l$ apply rules $S \rightarrow T$ and then (2) $\min(p, m - l) =: k$ times, and you get $$\underbrace{a\ldots{}a}_{l + k }T\underbrace{c\ldots{}c}_k\underbrace{d\ldots{}d}_{l = q}$$ If $k = p$ than $n$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $k = m -l$ and $a$ appears $l + k = m$ times. Apply rule $T \rightarrow V$, rule (4) $p - k$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{p - k}\underbrace{c\ldots{}c}_{k + p - k = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $p - k = n$ follows and you are finished.

3. Otherwise $q > l$, and you must apply rule $S \rightarrow U$, and rule (3) $\min(n, q - l) =: g$ times. You will get $$\underbrace{a\ldots{}a}_m\underbrace{b\ldots{}b}_gU\underbrace{d\ldots{}d}_{g + l}$$ If $g = n$ than $p$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $g = q - l$ and $d$ appears $l + g = q$ times. Apply rule $U \rightarrow V$, rule (4) $n - g$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{g + n - g}\underbrace{c\ldots{}c}_{n - g = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $n - g = p$ follows and you are finished.

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{eqnarray} S & \rightarrow & aSd \\ S & \rightarrow & T \\ S & \rightarrow & V \\ S & \rightarrow & U \\ S & \rightarrow & \epsilon \\ T & \rightarrow & aTc \\ T & \rightarrow & V \\ T & \rightarrow & \epsilon \\ U & \rightarrow & bUd \\ U & \rightarrow & V \\ U & \rightarrow & \epsilon \\ V & \rightarrow & bVc \\ V & \rightarrow & \epsilon \end{eqnarray} Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{align*} S & \rightarrow aSd \tag{1} \\ S & \rightarrow T \\ S & \rightarrow V \\ S & \rightarrow U \\ S & \rightarrow \epsilon \\ T & \rightarrow aTc \tag{2} \\ T & \rightarrow V \\ T & \rightarrow \epsilon \\ U & \rightarrow bUd \tag{3} \\ U & \rightarrow V \\ U & \rightarrow \epsilon \\ V & \rightarrow bVc \tag{4} \\ V & \rightarrow \epsilon \end{align*} Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{eqnarray} S & \rightarrow & aSd \\ S & \rightarrow & aTc \\ S & \rightarrow & bVc \\ S & \rightarrow & bUd \\ S & \rightarrow & \epsilon \\ T & \rightarrow & aTc \\ T & \rightarrow & bVc \\ T & \rightarrow & \epsilon \\ U & \rightarrow & bUd \\ U & \rightarrow & bVc \\ U & \rightarrow & \epsilon \\ V & \rightarrow & bVc \\ V & \rightarrow & \epsilon \end{eqnarray}

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminals $U$ and $V$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminals $T$ and $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{eqnarray} S & \rightarrow & aSd \\ S & \rightarrow & T \\ S & \rightarrow & V \\ S & \rightarrow & U \\ S & \rightarrow & \epsilon \\ T & \rightarrow & aTc \\ T & \rightarrow & V \\ T & \rightarrow & \epsilon \\ U & \rightarrow & bUd \\ U & \rightarrow & V \\ U & \rightarrow & \epsilon \\ V & \rightarrow & bVc \\ V & \rightarrow & \epsilon \end{eqnarray} Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.