Suppose that we take strings over the alphabet ∑ = {0,1}. Suppose w is a word, we defi ne sort(w) to be the word obtained by putting all the 0s before the 1s. Thus sort(010) = 001. Let L be any language. We de fine sort(L) = {sort(w)| w ∈ L}.
If L is regular does sort(L) have to be regular? Prove your answer. If your answer is "no" you have to give an explicit example of an L that is regular and a proof that sort(L) is not regular for your particular choice of L. If your answer is "yes" you have to give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L). Obviously a "yes" answer cannot be justi ed by an example. You must give a construction that works for any L.