Construct Context-Free Grammar for $\{a^ib^jc^kd^l : i,j,k,l\geq1\:\land\: i+j=k+l\}$

Question

One of the tasks on my exam was to construct a context-free grammar for the language:

$$L = \{a^ib^jc^kd^l : i,j,k,l\geq1\:\land\: i+j=k+l\}$$

I have no clue how to construct such a grammar, could someone help me?

Answer 1

If you think about how you might check the condition $i+j = k+l$, one way that comes to mind would be: repeatedly peel off an $a$ or a $b$ from the start, and at the same time peel off a $c$ or a $d$ from the end. If at any time you reach a string with only $a$ and $b$, then at the start you had $i+j > k+l$ so the string does not match the condition. Similarly, if you reach a string with only $c$ and $d$, then at the start you had $i+j < k+l$. But if you reach an empty string, then the total number of $a$ and $b$ matched the total number of $c$ and $d$.

However, on top of this, you have the restriction that once you've peeled off a $b$ from the start, you can never see $a$ at the start again; and similarly, once you've peeled off a $c$ from the end, you can never see $d$ at the end again. So, to reflect this, you will need to keep track of whether you've seen a $b$ peeled off from the left, and whether you've seen a $c$ peeled off from the right.

Keeping this in mind (as well as the fact that at the start, you must peel off an $a$ and a $d$ since $i, l \ge 1$), a grammar for the language could look something like:

\begin{align*} S \rightarrow & ~ a ~ ABCD ~ d \\ ABCD \rightarrow & ~ a ~ ABCD ~ d \\ | & ~ a ~ ABC ~ c \\ | & ~ b ~ BCD ~ d \\ | & ~ b ~ BC ~ c \\ ABC \rightarrow & ~ a ~ ABC ~ c \\ | & ~ b ~ BC ~ c \\ BCD \rightarrow & ~ b ~ BCD ~ d \\ | & ~ b ~ BC ~ c \\ BC \rightarrow & ~ b ~ BC ~ c \\ | & ~ \varepsilon \end{align*}

Here the grammar incorporates the requirement $j, k \ge 1$ in the fact that by the time you reach the "leaf" production $BC \rightarrow \varepsilon$, you must have peeled off $b$ on the left at least once, and also must have peeled off $c$ on the right at least once.