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 0*1 given by the pumping lemma. Choose s to be the string OP1P. 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. 1.30

Answer 1

The incorrect "proof" stated that 0*1* is not regular by using the pumping lemma incorrectly. The error is in claiming that a string s in this language cannot be pumped, which is false. The proper application of the pumping lemma shows that 0*1* is indeed a regular language.

Step-by-step explanation:

The erroneous "proof" provided in the question claims that the language 0*1* is not regular by using the pumping lemma. The assumption is that for the given regular language, there exists a pumping length p, and choosing a string s that belongs to this language cannot be pumped, which should lead to a contradiction. However, the mistake in this proof lies within the misunderstanding or misapplication of the pumping lemma.

The pumping lemma states that for any string that belongs to a regular language and has a length greater than or equal to the pumping length, there exist substrings x, y, and z such that s = xyz, with the conditions that |xy| ≤ p, |y| > 0, and xynz is in the language for every n ≥ 0. Since 0p1p is in the language 0*1* and meets the criteria of the pumping lemma, it can be divided into x = 0k, y = 0p-k, and z = 1p where 0 ≤ k < p. For any n ≥ 0, the string xynz will consist of a series of 0s followed by a series of 1s, which is the definition of strings in the language 0*1*. Therefore, the string can indeed be pumped, maintaining the regularity of the language.

The conclusion that 0*1* is not a regular language is incorrect, as it can be shown through proper application of the pumping lemma that it satisfies the properties of a regular language. The key misunderstanding revolved around incorrectly asserting that the chosen string could not be pumped.