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.
The hard part about these kinds of arguments is getting the quantifiers right. The pumping lemma says:
If $L$ is regular, then there exists a $p \ge 1$, such that for all $w \in L$ with $|w| \ge p$, there exists a "splitting" $w = xyz$, such that for all $i \ge 0$, $xy^iz \in L$.
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!)
Let $L$ be a language. If for all $p \ge 1$, there exists a $w \in L$ with $|w| \ge p$, such that for all "splittings" $w = xyz$, there exists an $i \ge 0$ such that $xy^iz \notin L$, then $L$ is not regular.
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$.
Best Answer
HINT: $L_1\cup L_2=L_2$, and $L_1\cap L_2=L_1$. For (d), note that you can design a DFA that handles the members of any finite collection of words, like $\{\lambda,ab,a^2b^2\}$, individually, and handles all other words separately.
Your use of the pumping lemma in (a) is correct.