Prove that the following language holds the pumping lemma for context-free languages: (Although it is not context-free)

L is a language under alphabet {a,b,c,d}

L={$a^ib^ic^j$ : i,j $\ge$ 0}∪{$a^kb^kd^{2n}c^k$ : k,n $\ge$ 0}

Point out what is the smallest pumping length m to which the pumping lemma holds.

I don't quite understand why the minimal pumping length is 2, the only one character word in L is c and the pumping lemma holds for it.

and there's no other one character word in L to my understanding. so shouldn't the minimal pumping lemma be 1?

  • $\begingroup$ The problem is not well-stated. If you mean "Prove that the following lemma fulfillss the conditions of the pumping lemma" then this cannot be done. Int first component, for $j=0$, any pumping in $a^ib^i$ will lead out of the language. The same in the second component for $n=0$. 2 is actually the smallest length where you can find words that cannot be pumped. For 0 and 1 you cannot. $\endgroup$ – Peter Leupold Feb 20 '18 at 17:25

tl;dr: try pumping $z=abddc$ with $n=1$.

This is a little tricky. You should remember that the pumping length $n$ is used twice in the lemma. First, it is used to claim that any word such that $|z|\ge n$ can be pumped. This is not relevant here; indeed, $c$ can be pumped. But it has a second use, limiting the size of the "pumpable" segment, which fails here for $n=1$.

Let's assume $n=1$ and observe the word $z=abddc\in L$. We need to find $z=uvwxy$ such that $|vwx|\le n$ and $uv^iwx^iy\in L$.

Since $n=1$ then $vwx$ must contain of exactly one letter (at least one, since $|vx|>0$ and at most one because $|vwx| \le 1$). If we choose $v=a$ then $i=0$ would yield $bddc\notin L$ and similarly we can't have $v=b$ or $v=c$. Choosing $v=d$ seems the obvious choice, but then for $i=0$ we'll end up with $abdc\notin L$ becuase $d$ should appear an even number of times. So you need at least $n\ge 2$ in order to be able to pump an even number of d's.


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.