19 views

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.

1. $\{0^{n}1^{m}0^{n}|m,n\geq 0\}$
2. $\{0^{m}1^{n}|m\neq n\}$
3. $\{w|w\in\{0,1\}^{*} \text{is not a palindrome}\}$
4. $\{wtw|w,t\in\{0,1\}^{+}\}$
| 19 views