I have an example from a textbook using a language $L = \{ a^nb^ma^n : m, n \ge 0, n \ge m \}$.
We can use pumping theorem to show that $L$ is not context-free. If it were, then there would exist some $k$ such that any string $w$, where $|w| \ge k$, must satisfy the conditions of the theorem. We show one string $w$ that does not. Let $w =a^kb^ka^k$ where $k$ is the constant from the pumping theorem [...]
- Why have they chosen to use $k$? My understanding from the pumping theorem definition is that $k$ is an arbitrary integer $>1$
- What is the relation of $k$ to $n$ and $m$ in the original language definition?
- Members of $L$ can have more $a$'s than $b$'s, but $a^kb^ka^k$ will result in an equal number of $a, b$. Is it not necessary in this case because an equal number of $a$'s and $b$'s is still a member of L? What happens when $L = \{ a^nb^ma^n : m, n \ge 0, n > m \}$ and $a^kb^ka^k$ is not part of $L$?
I think this is holding me back from understanding how to prove my homework question of:
Prove whether the language $\{a^xb^yc^xd^y: x, y \ge 0\}$ is context free or not
Apologies if these are basic. I've been racking my brain for days on these kinds of questions and I'm so lost. Thanks for any assistance.