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