Question 1.46: Prove that the following languages are not regular. You may ...
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement.
a. \left\{0^{n} 1^{m} 0^{n} \mid m, n \geq 0\right\}
{ } ^{A} b. \left\{0^{m} 1^{n} \mid m \neq n\right\}
c. \left\{w \mid w \in\{0,1\}^{+} \text {is not a palindrome }\right\}^{8}
{ }^{*} \mathrm{~d} . \quad\left\{w t w \mid w, t \in\{0,1\}^{*}\right\}
(b) Let B= \left\{0^{m}1^{n} \mid m\neq n \right\}. Observe that \overline{B} \cap 0^{*}1^{*} = \left\{0^{k} 1^{k} \mid k\geq 0 \right\}. If B were regular, then \overline{B} would be regular and so would \overline{B} \cap 0^{*}1^{*}. But we already know that \left\{0^{k} 1^{k} \mid k\geq 0 \right\} isn’t regular, so B cannot be regular.
Alternatively, we can prove B to be nonregular by using the pumping lemma di-rectly, though doing so is trickier. Assume that B= \left\{0^{m}1^{n} \mid m\neq n \right\} is regular. Let p be the pumping length given by the pumping lemma. Observe that p! is di-visible by all integers from 1 to p, where p != p (p-1)(p-2)…1. The string s= 0^{p} 1^{p+p!} \in B, and \left|s\right| \geq p. Thus the pumping lemma implies that s can be divided as xyz with x= 0^{a} , y= 0^{b}, and z= 0^{c} 1^{p+p!}, where b\geq 1 and a + b + c = p.
Let s^{\prime } be the string xy^{i+1}z, where i= p!/ b. Then y^{i} = 0^{p!} so y^{i+1} =0^{b+p!}, and so s^{\prime }= 0^{a+b+c+p!} 1^{p+p!}. That gives s^{\prime }=0^{p+p!}1^{p+p!} \notin B, a contradiction.