In this class we will talk about alphabets A and languages L. An alphabets A is any non-empty nite set. We let A* be the set of all nite strings of elements from A. So A* is innite. Languages are sets whose elements come from some A, so they are subsets of A. Consider the language L = { x | x is a binary string starting with 11 and ending with a 1 followed by an even number of 0s} = { x | x = 11y10t where y {0,1} and t 2 is even }.

1). Give an example of a subset B of L which is innite and for which L-B is also innite. 2) Give an example of a language K with the same alphabet as L and such that K-L = { 0111, 100, 11, 000, 1010000 }.

3) True or false: Any two languages are equal if and only if they have the same elements