0
$\begingroup$

I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma

If L = {ambncndn | m,n >= 1 }

Should I have n be the constant of the pumping lemma? Is z=ambncndn and |z|= m+3n>n ?

By the pumping lemma, there exist u,v,w,x,y such that z=uvwxy, |vwx| <=n, |vx|>=1 . I'm just a little thrown off by the two different letters for the exponents, can I treat m and as another n?

$\endgroup$
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Mar 15 '16 at 7:37
0
$\begingroup$

You want to show that the language $L = \{a^mb^nc^nd^n \mid m,n\ge 1 \}$ does satisfy the Pumping Lemma (for context-free languages) while it is not context-free.

In order to do so, you must show that every string can be pumped within the language, so for every string $z=a^mb^nc^nd^n$ (for large enough $m+3n$) you must find a decomposition $z=uvwxy$ that can be pumped. The problem however is that your language $L$ does not satisfy the Pumping Lemma. Possibly?) you wanted to pump the first $a$ in a string (taking $u=x=y=\lambda$, $v=a$, $w=a^{m-1}b^nc^nd^n$). Generally that works, but not if the string contains a single $a$, like $ab^nc^nd^n$. Then we can pump the letter $a$ `down' choosing $i=0$ which results in a string outside of $L$. All other decompositions will fail (they will destroy the $abcd$ order or the equal numbers of $b,c,d$).

An example of a non-regular language that satisfies the Pumping Lemma (for regular languages) can be found here: Languages that satisfy the pumping lemma but aren't regular? .

It is of a very specific form $\$\cdot K \cup \{\$^k \mid k\neq 1\}\cdot \Sigma^*$ (for a complicated language $K$) that can be used for context-free pumping examples too.

$\endgroup$
0
$\begingroup$

Assume that pumping lemma is satisfied for $L$. Let $N$ be the pumping length.

Now take $z = ab^Nc^Nd^N \in L$. $|z| = 3N+1$ and hence this string can be pumped.

For this string, every choice of $u,v,w,x$ and $y$ that satisfies the conditions of pumping lemma will have a choice of $i \in \mathbb{N}$ such that $uv^iwx^iy \not\in L$. This is a contradiction. Hence $L$ is not context-free.

$\endgroup$

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.