Homework 2

Due: April 3, 2001

The language *L* is defined to be the set of strings of 0's
and 1's of the form *w**w'*, where *w'* is formed from
*w* by replacing all 0"s by 1's, and vice-versa; e.g., for
*w*=011, *w'*=100. Therefore, 011100 is in *L*. Prove
that *L* is not regular.