⟸ pàgina anterior ⟸

Exercici 9 (Tasca 1).

(theory of languages, shift)

Desplaçament d’un llenguatge

Donat un llenguatge L, definim el desplaçament de L, que denotem S(L) (de shift), com el llenguatge que conté els mots obtinguts aplicant un desplaçament circular a cada mot de L de totes les maneres possibles; formalment, S(L)=\{vu\mid uv\in L\}. Argumenteu si les afirmacions següents són certes (amb una justificació) o falses (amb un contraexemple) per qualsevol 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)), on \sigma és un homomorfisme.