1
$\begingroup$

I know why cases 1 and 2 are wrong because our language can have different numbers of 0's and 1's. But I'm not sure how case 3 can be proved wrong for our language.

Exercise 1.30: Describe the error in the following “proof” that $0^{∗}1^{∗}$ is not a regular language. (An error must exist because $0^{∗}1^{∗}$ is regular.)

The proof is by contradiction. Assume that $0^{∗}1^{∗}$ is regular. Let p be the pumping length for $0^{∗}1^{∗}$ given by the pumping lemma. Choose s to be the string $0^{p}1^{p}$. You know that s is a member of $0^{∗}1^{∗}$, but Example 1.73 shows that s cannot be pumped. Thus you have a contradiction. So $0^{∗}1^{∗}$ is not regular.

Example 1.73:

Let B be the language $\{0^{n}1^{n}|n ≥ 0\}$. We use the pumping lemma to prove that B is not regular. The proof is by contradiction. Assume to the contrary that B is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string $0^{p}1^{p}$. Because s is a member of B and s has length more than p, the pumping lemma guarantees that s can be split into three pieces, s = xyz, where for any i ≥ 0 the string $xy^{i}z$ is in B. We consider three cases to show that this result is impossible.

  1. The string y consists only of 0s. In this case, the string xyyz has more 0s than 1s and so is not a member of B, violating condition 1 of the pumping lemma. This case is a contradiction.
  2. The string y consists only of 1s. This case also gives a contradiction.
  3. The string y consists of both 0s and 1s. In this case, the string xyyz may have the same number of 0s and 1s, but they will be out of order with some 1s before 0s. Hence it is not a member of B, which is a contradiction.

Thus a contradiction is unavoidable if we make the assumption that B is regular, so B is not regular. Note that we can simplify this argument by applying condition 3 of the pumping lemma to eliminate cases 2 and 3. In this example, finding the string s was easy because any string in B of length p or more would work.

This question is from the book 'Introduction to the Theory of Computations' by Michael Sipser, exercise 1.30

$\endgroup$
3
  • $\begingroup$ This has nothing to do with $\lambda$ calculus. $\endgroup$ – Yuval Filmus Feb 25 at 9:25
  • $\begingroup$ I'm sorry the tag must have been added by mistake! @YuvalFilmus $\endgroup$ – Ellie Feb 25 at 9:48
  • $\begingroup$ I did not know we had to cite the book we take it from, I have corrected that and added it! Thank you! @greybeard $\endgroup$ – Ellie Feb 25 at 9:49
1
$\begingroup$

The pumping lemma states that if $L$ is regular then there exists a constant $p$ such that any word $w \in L$ of length at least $p$ can be decomposed as $w = xyz$ so that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, and (iii) $xy^iz \in L$ for all $i \geq 0$.

The pumping lemma does not state that any decomposition which satisfies properties (i),(ii) also satisfies property (iii).

The pumping lemma only guarantees that some decomposition which satisfies all three properties exists.

In your case, you can take $p = 1$. If $w = 0^n1^m$ for $n \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 0$, $z = 0^{n-1} 1^m$. If $w = 1^m$ for $m \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 1$, $z = 1^{m-1}$.

$\endgroup$
1
  • $\begingroup$ Oh! I was assuming that all decompositions should satisfy all three properties. This makes sense. Thank you! $\endgroup$ – Ellie Feb 25 at 9:46
1
$\begingroup$

The cases 1 and 2 don't work because unlike the language in example 1.7.3, your language allows strings with different number of 0's and 1's.

Therefore you have no contradiction and no proof that the language is irregular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.