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.
0
$\begingroup$
$\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$
$\endgroup$
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 \}$.
-
$\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
