Problem Detail: I have a question about a specific pumping lemma problem for Context-Free Languages. Suppose we have the following Language:
$L = {a^{i}b^{j}c^{k}d^{l} mid 0 < i < k wedge j > l > 0 }$
Here is my attemp to prove that the language is not context-free: Assume $L$ is context-free. Let $n>0$ be the pumping length given by the lemma. Let $z = a^{n}b^{n+1}c^{n+1}d^{n}$, then $z in L$. Than according to the lemma, $z$ can be written as $z = uvwxy$ where the following properties hold:
- $|vx| geq 1$
- $|vwx| leq n$
- for every $i geq 0$, $uv^{i}wx^{i}y in L$.
We have 6 different possibilities for $vwx$:
- $vwx = a^{i}$ where $i leq n$
- $vwx = a^{i}{b^j}$ where $i+j leq n$
- $vwx = b^i$ and $i leq n$
- $vwx = b^{i}c^{j}$ and $i+j leq n$
- $vwx = c^{i}$ with $i leq n$
- $vwx = c^{i}d^{j}$ and $i+j leq n$
Is this right so far? The thing that I’m unsure of is if my different cases for $vwx$ are right. How do I choose the pumping length for case 2? If I choose $i$ = 2, what if $i$ is zero ? Then I don’t have any contradiction. Thanks in advance
Asked By : mrjasmin
Answered By : Yuval Filmus
Let me rephrase property 3 of the pumping lemma: for every $l geq 0$, $uv^lwx^ly in L$. Now let’s consider the seven different cases: Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n notin L$. Case 2: $vx = a^ib^j$ where $i,j > 0$. Like case 1 or case 3. Case 3: $vx = b^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1-i} c^{n+1} d^n notin L$. Case 4: $vx = b^ic^j$ where $i,j > 0$. Like case 3 or case 5. Case 5: $vx = c^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1} c^{n+1-i} d^n notin L$. Case 6: $vx = c^id^j$ where $i,j > 0$. Like case 5 or case 7. Case 7: $vx = d^i$ where $i > 0$. Choose $l = 2$ to get $a^n b^{n+1} c^{n+1} d^{n+i} notin L$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7740
