For any string w, let contract(w) denote the string obtained by collapsing each maximal substring of...

 

Transcribed Image Text:

For any string w, let contract(w) denote the string obtained by collapsing each maximal substring of equal symbols to one symbol. For example: contract(010101) = 010101 contract(001110) = 010 contract(111111) = 1 contract(1) = 1 contract(&) = Prove that for every regular language L over the alphabet {0,1}, the following languages are also regular: (a) contract(L) = {contract(w) | wL} (b) contract (L) = {w = {0, 1}* | contract(w) = L} For any string w, let contract(w) denote the string obtained by collapsing each maximal substring of equal symbols to one symbol. For example: contract(010101) = 010101 contract(001110) = 010 contract(111111) = 1 contract(1) = 1 contract(&) = Prove that for every regular language L over the alphabet {0,1}, the following languages are also regular: (a) contract(L) = {contract(w) | wL} (b) contract (L) = {w = {0, 1}* | contract(w) = L}

Answer rating: 100% (QA)

To prove that for every regular language L over the alphabet 0 1 the languages contractL and contrac... View the full answer