How to calculate the minimum pumping length for some L?

3k Views Asked by At

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 \mid i,j \ge 0\} \cup \{a^kb^kd^{2n}c^k \mid 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?

1

There are 1 best solutions below

2
On

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.