0
$\begingroup$

Can anyone help with the following problem ?

Let $B = \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$, use the pumping lemma to prove B is not context-free

Thanks in advance.

$\endgroup$
  • 3
    $\begingroup$ Sorry, but $B$ is context-free. $\endgroup$ – Hendrik Jan Oct 6 '18 at 11:37
  • $\begingroup$ Sorry, you are right, there is probably a mistake in the description of the exercise. $\endgroup$ – ElDon90 Oct 7 '18 at 8:26
3
$\begingroup$

Consider the following Context Free Grammar $G$:

$S \rightarrow aSdd\ |\ X\ |\ \epsilon$
$X \rightarrow bXc\ |\ \epsilon$

The language $L(G)$ generated by $G$ corresponds to the set of all the strings $\{\epsilon, add, aadddd, ..., bc, bbcc,..., abcdd, abbccdd,...\}$.
More generally, it corresponds to $ \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$.

$\endgroup$
  • $\begingroup$ Sorry, you are right, there is probably a mistake in the description of the exercise. The language is context-free $\endgroup$ – ElDon90 Oct 7 '18 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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