Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

Let $L=\{a^mb^nc^k\mid k\le \min(m,n)\}$

$L$ can be pumped with the pumping lemma for Context Free Languages which makes it very difficult to prove it is not a Context Free Language.

Any idea how to prove such a tricky case?

This is homework of course.

share|improve this question
Can you show your attempt at applying the pumping lemma to L? It seems like the pumping lemma would work - note that the pumping lemma allows characters to be pumped zero times as well. – donburi Jan 14 at 21:05
I know it will work, that is the tricky part because the easy way to prove a language is not a CFL is contradict the pumping lemma which can't be done it that case. – Yoni Hassin Jan 14 at 21:10
1  
@donburi I don't think pummping zero times will work. Since you have $vxy$ you can always make $v=a \text{ or }b$ and $y=c$, in which case pumping zero times can't change anything. – JSchlather Jan 14 at 21:37
After further reading i realized it has to proven with Ogden's lemma. Still working on that.. – Yoni Hassin Jan 14 at 23:28

1 Answer

up vote 1 down vote accepted

Hint: Suppose L is regular and the pumping length is $n$, then consider the string $w = a^{n}b^{n}c^{n} \in L$. By the pumping lemma, there exists a decomposition $w = uvxyz$ such that $\left|vxy\right| \leq n$ (and $\left|vy\right| \gt 0$) and $uv^ixy^iz \in L$ for all $i \in \{0, 1, 2, \ldots\}$. What are the possibilities for $vxy$?

share|improve this answer
Are we speaking about the pumping lemma for CFL's? Because $vxy$ can be $a^tb^s$,$t+s \le n$ so $w$ can be pumped and nothing can be proved here, i am wrong? – Yoni Hassin Jan 14 at 23:45
1  
Suppose $vxy$ were $a^tb^s, t + s \leq n$. Then what is $uv^0xy^0z$? – donburi Jan 15 at 0:02
$a^{n-t}b^{n-s}c^n$ ? And using the fact that $t+s>0$ proves the whole thing? Actually you claim that $L$ can not be pumped for any partition of $w=uv^ixy^iz$ ? – Yoni Hassin Jan 15 at 9:13
1  
You still have to check all the other possibilities: $vxy$ is all $a$, all $b$, or all $c$, or is $b^tc^{n-t}$, but it's not too difficult to show that they don't work either. – donburi Jan 15 at 18:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.