Question

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 compliment.

a){}

0"1"0" m,n>0

b){ $0^{m}1^{n}| m \neq n$ }

c) { $w| w \epsilon \left \{0 \right, 1\}*$ is not a palindrome}

*d) $\{wtw| w,t \epsilon \left \{ 0 \right 1\}+ \right\}$ }

Answer 1

Solution:

a)

(0^n 1^n 0^n}
Since, Regular languages are dosed under union, intersection and complement. L U 0^n1^m0^n = {0^n1^m0^n, m,n >= 0 } is irregular

b. 10m 1 m n) Since Regular languages are closed under union, intersection and complement. . L '. 0rn In = {Om 1n m = n} is irregular. c. (w wE (o, 1)' is not a palindrome) Since Regular languages are closed under union, intersection and complement. . l." От 1: {0m In m n) is irregular. Since Regular languages are closed under union, intersection and complement. .Ln0 1 U1) (O U1 (OU 1) m, n 20) is iregular

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)