3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ Hint: $m=l+k$ is the crucial property. (Our reference question may be of some help.) $\endgroup$
    – Raphael ♦
    Nov 4, 2014 at 11:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Rick Decker
    Nov 4, 2014 at 16:14
  • $\begingroup$ answers can be found here: cs.stackexchange.com/questions/18126/… $\endgroup$
    – Ran G.
    Feb 12, 2015 at 2:58

1 Answer 1

Reset to default
1
$\begingroup$

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$

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.