⟸ Go Back ⟸

Exercise 9 (Homework 1).

(theory of languages, shift)

Shifting a language

Given a language L, we define the shift of L, denoted S(L), as the language that contains the words obtained by applying a circular shift to each word in L in all possible ways; formally, S(L) = \{vu\mid uv\in L\}. Argue whether the following statements are true (with a justification) or false (with a counterexample) for any L.

1. S(L)^*\subseteq S(L^*).
2. S(L)^*\supseteq S(L^*).
3. \overline{S(L)}=S(\overline{L}).
4. S(L^R)=S(L)^R.
5. S(L_1\cup L_2)=S(L_1)\cup S(L_2).
6. S(L_1\cap L_2)=S(L_1)\cap S(L_2).
7. S(L_1L_2)=S(L_1)S(L_2).
8. S(\sigma(L))=\sigma(S(L)), where \sigma is a homomorphism.