Question

Question: 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 localid="1662103472623" $0*1*$given by the pumping lemma. Choose s to be the string 0p1p . 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.

Short answer

The above problems arise when the pumping lemma is used on a language which is regular since violating a condition of the pumping lemma indicates that the language is non-regular but the vice versa is not always true.

Step-by-step solution

Introduction 

The pumping lemma is used as a poor check to prove that the given language is non-regular. The language that violates the any of the three situations of the pumping lemma is classified as non-ordinary.

Because the pumping lemma starts off evolved by assuming that the given language is regular, the belongingness of the string, that is used as a counter instance, is examined most effective for the given language and now not for all the languages that accepts the string.

Explanation

The proof given in the example 1.73 (refer to the textbook example 1.73) is for a different language. The counter examples given to prove the language as non-regular does not hold true for the language given in the question as shown below:

Let A be the language$\left\{0*1*\right\}$given in the question.

Let B be the language localid="1662104151400" $\{0n1n\overline{)n}>=0\}$given in the example 1.73.

As per the example 1.73,s is op1p and hence as per the pumping lemma, s should be split into three pieces as s=xyz , where for any i>=0, the string xyyz is in B . The cases are as follows:

The string y contains all 0s: The string xyyz will result in more number of 0 s than the number of 1 s which does not belong to the language B but the string belongs to language A and hence, the pumping lemma is not violated.

The same reason holds true for the case when the string y contains all 1 s. The string xyz will results in more number of 1 s which is again accept by the given language A .

Since the above conditions are satisfied, the given language cannot be classified as non-regular by pumping lemma.

Therefore, the error in the given proof is that a string which is used as a counter example to prove a certain language as non-regular does not signifies that all the languages that accept that string are considered as non-regular.

The above problems arise when the pumping lemma is used on a language which is regular since violating a condition of the pumping lemma indicates that the language is non-regular but the vice versa is not always true.