CS 476
Homework 2

Assigned: March 27, 2001
Due: April 3, 2001

The language L is defined to be the set of strings of 0's and 1's of the form ww', 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.