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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityCan 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.
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 \}$.