Question: For words, w , u , v in , if we can write w = uv , then we can define a cyclic shift of

For words, w, u, v in , if we can write w = uv, then we can define a cyclic shift of the w as vu. For example, the word w = abca has four cyclic shifts: bcaa, caab, aabc, and abca. Define c(w, k) to be the (left) cyclic shift by k symbols. So, c(abca,0)= abca, c(abca,1)= bcaa, c(abca,2)= caab, and c(abca,3)= aabc. For any language L, we define CS(L)={x : x in L and c(x, k) in L,0 k <|x|}. For example, if L ={a, b, ba, ab, bbb, aba, aab}, then CS(L)={a, b, ab, ba, bbb}, since a = c(a,0) and b = c(b,0), ab = c(ba,1) and ba = c(ab,1), and bbb = c(bbb,0)= c(bbb,1)= c(bbb,2). Note that c(aba,1)= c(aab,2)= baa in L, and thus aba in CS(L) and baa in CS(L).(a) If L is recursive, is CS(L) also recursive? Justify your answer. (b) If L is recursively enumerable, is CS(L) also recursively enumerable? Justify your answer.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!