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. Theory of Computation michael-sipser theory-of-computation finite-automata pumping-lemma proof + – admin asked Apr 21, 2019 edited Apr 22, 2019 by Lakshman Bhaiya admin 892 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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. narges answered Nov 14, 2021 narges comment Share Follow See all 0 reply Please log in or register to add a comment.