# Creating a CFG that connects lengths of three blocks [duplicate]

I have to create a CFG which generates

$$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$

The first part is easy enough, I came up with

\begin{align*} S &\to aS_2abS_3 \\ S_2 &\to aS_2ab \mid \epsilon \end{align*}

However, the second part is very confusing. So far I have

$$S_3 \to S_4 \mid \epsilon$$

The problem I have is how do I possibly keep track of all of these variables? $k$ has to be less than $m$, $m$ has to be equal to $\ell + k$, and $\ell$ must be at least $1$ by extension. Can someone give me some general tips for approaching these CFG's?

• Hint: $m=l+k$ is the crucial property. (Our reference question may be of some help.)
– Raphael
Nov 4, 2014 at 11:39
• To amplify @Raphael's comment, note that $c^md^\ell e^k=c^kc^\ell d^\ell e^k$. From here, the construction should be clear. Nov 4, 2014 at 16:14
• answers can be found here: cs.stackexchange.com/questions/18126/… Feb 12, 2015 at 2:58

Here comes the grammar based on your part of the answer and the comments of Raphael and Rick Decker (including $l\ge 1$). At first, your part:
$S\to aA_1abA_2$
$A_1\to aA_1ab\mid\varepsilon$
Secondly, we create rules for $A_2$ such that we get words of the form $c^kA_3e^k$
$A_2\to cA_2e\mid A_3$
Finally, we create rules for $A_3$ such that we get words $c^ld^l$ with $l\ge1$:
$A_3\to cA_3d\mid cd$