Think of the Pumping Lemma as a game in which you're trying to prove that a language isn't regular, while someone else is "defending" the regularity of this language. Here is how to play the game:
- The defender specifies the pumping length $n$. Think of it as the number of states in the automata that recognizes the language.
- You give the defender a word $w$ from the language that satisfies the condition: $|w| \ge n$.
- The defender divides this word into $xyz$, where $|xy| \le n$ and $|y| > 0$. This division must also satisfy the condition that $xy^{k}z$ belongs to the language $\forall k \ge 0$.
If you give the defender a word that is impossible to divide under the conditions in step 3, you win and the language isn't regular.
Given the above, let's have a look at your answer. You gave the word $0^{n}1^{n-1}$. I'll play the role of the defender and divide it as: $0^{n-1}01^{n-1}$ where $x = 0^{n-1}$, $y = 0$ and $z = 1^{n-1}$. This division satisfies all of the conditions above:
- $|xy| = |0^n| \le n$
- $|y| = |0| = 1 \ge 0$
- $xy^{k}z = 0^{n-1}0^{k}1^{n-1} = 0^{n+k-1}1^{n-1} \in L$
The last condition is justified because:
$$
k \ge 0 \Rightarrow n+k-1 \ge n-1
$$
Thus, your word doesn't make it impossible for me to divide the word in a way that satisfies the Pumping Lemma's conditions.
Now, what if we consider $0^{n}1^{n}$ instead? No matter how I divide it, $x$ and $y$ will always fall within the $0^n$ part since $|xy| \le n$. Therefore, $y$ will consist of one or more $0$s. For $k = 0$, one or more $0$s will be removed and the number of $0$s in the string will be less than the number of $1$s, and the word will no longer be in the language. Hence, the language isn't regular.
Your proof is incorrect, for instance you only handle a subset of palindromes (and regular languages can have non-regular subsets). I'm not quite sure what you're trying to do there, but for reference here's my version of the proof using the pumping lemma. I hope it opens up valuable insights.
In the proof, I will assume the alphabet to consist of at least two distinct symbols (as palindromes are a regular language if there is only one symbol in the alphabet).
My version of the proof
(using $s^R$ to denote the reverse of $s$)
Let $L = \{s : s = s^R\}$ or the set of all palindromes (strings that are equal to their reverse strings).
If $L$ is regular, there must be a pumping length $p \ge 1$ so that for each $s \in L$, if $|s| \ge p$ we can write $s$ as $xyz$ so these three conditions apply:
- $y \neq \epsilon$ ($y$ has at least one character/symbol, in other words $|y| \ge 1$)
- $|xy| \le p$
- for all $i \in \mathbb{N} \cup \{0\}$, $xy^iz \in L$
Let $s = a^pba^p$. We can see $s$ is a palindrome, so $s \in L$. Also, $|s| = 2p + 1 \ge p$.
Because of the two first conditions, all possible $xyz$ divisions of $s$ are in the following form:
- $x = a^k$
- $y = a^m$
- $z = a^{p-m-k}ba^p$
for some non-negative integers $k, m$ so that $k + m \le p$ and $m \ge 1$.
Now let's demonstrate that $xy^iz \in L$ doesn't hold for some values of $i$.
For example, let $i = 2$. Then $$xy^2z = xyyz = a^ka^ma^ma^{p-m-k}ba^p$$
which can be simplified further as $$a^ma^pba^p = a^{p+m}ba^p$$
The reverse string, $(xy^2z)^R$ is $a^pba^{p+m}$. Because we know that $m \ge 1$, it follows that $$a^pba^{p+m} \neq a^{p+m}ba^p$$ Therefore, $xy^2z \notin L$ under any possible divisions $xyz$ while following the three conditions ruled by the lemma. Hence, $L$ must be non-regular.
Two important notes
- You can choose any string $s \in L$, as long as $|s| \ge p$. Make life easy for yourself and pick a string that makes the rest of the lemma easy to apply. I picked $a^pba^p$ simply to reduce the complexity of different $xyz$ divisions.
- For a language to be non-regular, you must prove there are no possible divisions $xyz$ that are possible according to the three criteria. It's not enough to demonstrate that some $xyz$ division fails at the $xy^iz \in L$ phase.
Best Answer
The hard part about these kinds of arguments is getting the quantifiers right. The pumping lemma says:
You can think of this as an adversarial game. You pick a $p$, your opponent picks a $w$, you pick the $xyz$, they pick the $i$. If you can show it's in $L$, you win. So, the pumping lemma can be thought of as: if $L$ is regular, you can always win this game.
Therefore, if you lose, the language is not regular. So let's switch the roles; you are now the aggressor. Your opponent picks a $p$, you pick a $w$, they pick a splitting, you pick an $i$, and if you can always win, then $L$ is not regular. This can be phrased more mathematically: (note that the quantifiers are now switched!)
So when proving languages are not regular, you don't get to pick how it splits!
What we have to do is pick our $w$ very carefully. I'll phrase this as a game first, then as a proof.
Let your opponent pick $p$. We'll choose $w = a^pbba^p$. No matter how our opponent splits the string, the conditions of the game/lemma require that $|xy| \le p$. So $xy$ consists only of $a$s, and cannot contain the $b$s. We choose $i = 0$, which will cause the $a$s to be asymmetric, and $xz \notin L$.
Assume $L$ is regular, for the sake of contradiction. Then $L$ satisfies the pumping lemma, so let $p$ be the pumping length. Consider $w = a^pbba^p$, where $a, b \in \Sigma$, $a \ne b$. Since $|w| = 2p + 2 \ge p$, there is some splitting $w = xyz$ satisfying the lemma. Since we know $|xy| \le p$, it must be that $x = a^k$ and $y = a^\ell$, with $k + \ell \le p$ and $\ell > 0$. This means that $z = a^{p-k-\ell} bb a^p$. Let $i = 0$, which gives $xz = a^{p - \ell} bb a^p$, which is not in $L$. By contradiction, $L$ is irregular.
By "splitting", I mean strings $x$, $y$, $z$ in $\Sigma^\ast$ such that $w = xyz$, $|xy| \le p$, and $|y| > 0$.