Formal Languages – Application of Pumping Lemma for Regular Languages

formal-languagesregular-language

I need to proof by using the Pumping lemma that the language $L = \{0^m1^n \;|\; m \geq n\}$ is not regular.

According to the Pumping lemma for each regular language a word $w = xyz$ exists, that $$\forall n,k \in \mathbb{N} \text{ with } 0 < |y| \leq |xy| \leq n$$ applies: $$xy^kz \in L$$

I'm not sure how to build the word w. This is what I've tried:

$$w = 0^n1^{n-1}, x = \lambda, y = 0^n \Rightarrow |xy| = n \leq n$$ (condition of Pumping lemma).

If I set k to $0$ I get $$w = xy^0z = xz = \lambda z = z = 1^{n-1} \not\in L$$ because $$|_1w| = n-1 > |_0w| = 0 $$
$\Rightarrow L $ ist not regular.

The only restriction for my proof is $k > 0$.

Is this right? Thanks in advance!

Best Answer

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:

  1. The defender specifies the pumping length $n$. Think of it as the number of states in the automata that recognizes the language.
  2. You give the defender a word $w$ from the language that satisfies the condition: $|w| \ge n$.
  3. 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.

Related Question