0
$\begingroup$

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to determine all the case studies.

A language that I want to use the pumping lemma for is $R = {a^{2j} b^k c^j b^k a^j}$

So this is what I understand:

You have to assume that the above language is context free and that the pumping lemma applies with a large number n.

You have to consider a string 'w' which is written in the form of w=uvxyz where |xyz| <= n ,|x| > 0 or |y| > 0, and |v|+|y|>0

Now, the real difficulty I am having is identifying the string w. I have $w = a^{2n} b^n c^n b^n a^n$

I am also having difficulty identifying the cases.

I have the following possible cases:

1) The substring xyz is covered in $a^{2n}$

2) The substring xyz is covered in $b^n$

3) The substring xyz is covered in $c^n$

4) The substring xyz is covered in $b^n$

5) The substring xyz is covered in $a^n$

6) xyz between $a^{2n}$ and $b^n$

7) xyz between $b^n$ and $c^n$

8) xyz between $c^n$ and $b^n$

9) xyz between $b^n$ and $a^n$

Now, is my choice of string w right? As is $w = a^{2n} b^n c^n b^n a^n$ correct? If not, what should the string w be?

Also, are my case studies correct? If not, what should they be?

Pumping lemma seems to be extremely difficult to grasp, especially with more than two letters (a,b,c)

It would give me less of a headache and more of an understanding if someone could help me answer the question. I attempted it, but I got stuck after seeing the 'c'

Thanks

$\endgroup$
  • $\begingroup$ Remember that at a high level, the pumping lemma says: All sufficiently long strings in the language can be broken up as $uvxyz$ in such a way that $uv^ixy^iz$ is in the language for every $i$. For your language, what could $v$ or $y$ be? Consider if they contain only one symbol (possibly repeated many times) vs. multiple distinct symbols. $\endgroup$ – William Hoza Dec 1 '15 at 1:31
  • $\begingroup$ @WilliamHoza, thats the thing. I don't know what $uv^i xy^i z$ is. I don't know what v and y is! I am confused by it all $\endgroup$ – Samserso Deskanson Dec 1 '15 at 1:37
0
$\begingroup$

If $n$ is the pumping length, your choice of $w=a^{2n}b^nc^nb^na^n$ is fine. However, the pumping lemma says that $w$ can be decomposed as $w=uvxyz$ in such a way that $|vxy|\le n$, $|vy|\ge 1$, and $uv^kxy^kz\in R$ for each $k\ge 0$. The possibilities that you’ve enumerated for $xyz$ are actually possibilities for $vxy$. To finish the argument, show that no matter which of these possibilities holds, $uv^0xy^0z=uxz\notin R$.

$\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.