edited by
892 views
0 votes
0 votes
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. Chooses 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.
edited by

1 Answer

0 votes
0 votes
The error is that s = 0p1p can be pumped. Let s = xyz, where x = 0, y = 0 and
z = 0p−21p. The conditions are satisfied because
i) for any i ≥ 0, xyiz = 00i0p−21p is in 0∗1∗.
ii) |y| = 1 > 0, and
iii) |xy| = 2 ≤ p.

Related questions

1 votes
1 votes
1 answer
4