Tema 1.   Teoria de Llenguatges

1. ($a$)  
   ​

   Llenguatge dels mots sobre $\{a,b\}$ que contenen el submot $ab$.

2. ($b$)  
   ​

   Llenguatge dels mots sobre $\{a,b\}$ tals que a la dreta de cada submot $ab$ hi ha algun submot $ba$.

3. ($c$)  
   ​

   Llenguatge dels mots sobre $\{a,b\}$ que contenen el submot $ab$ i el submot $ba$.

4. ($d$)  
   ​

   Llenguatge dels mots sobre $\{a,b,c\}$ tals que entre cada dues $b$’s hi ha alguna $a$.

5. ($e$)  
   ​

   Llenguatge de mots sobre $\{a,b\}$ tal que tota ocurrència de $b$ està en posició parell (el primer símbol d’un mot ocupa la posició $1$).

6. ($f$)  
   ​

   Llenguatge dels mots sobre $\{a,b\}$ amb algun prefix amb més $b$’s o igual que $a$’s.

7. ($g$)  
   ​

   Llenguatge dels mots sobre $\{a,b\}$ tals que qualsevol prefixe seu té més $b$’s o igual que $a$’s.

8. ($h$)  
   ​

   Llenguatge dels mots sobre $\{a,b\}$ amb algun prefix de mida parell amb més $b$’s o igual que $a$’s.

9. ($i$)  
   ​

   Llenguatge dels mots sobre $\{a,b\}$ tals que qualsevol prefixe seu de mida parell té més $b$’s o igual que $a$’s.

10. ($j$)  
    ​

    Llenguatge dels mots sobre $\{a,b\}$ que tenen un prefix i un sufix idèntics de mida major que 0 i menor que la mida del propi mot.

Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions sobre mots $x,y,z$ i llenguatges $A,B,C$ en general.

1. ($a$)  
   ​

   $xy=yx$.

2. ($b$)  
   ​

   $xy=xz\Rightarrow y=z$.

3. ($c$)  
   ​

   $A(BC)=(AB)C$.

4. ($d$)  
   ​

   $AB=BA$.

5. ($e$)  
   ​

   $A\not=\emptyset\;\wedge\;AB=AC\;\Rightarrow\;B=C$.

6. ($f$)  
   ​

   $A\not=\emptyset\;\wedge\;B\not=\emptyset\;\wedge\;AB=CD\;\wedge\;(\forall u\in A,v\in C:|u|=|v|)\;\Rightarrow\;A=C\;\wedge\;B=D$.

7. ($g$)  
   ​

   $(A\cup B)C=AC\cup BC$ i $A(B\cup C)=AB\cup AC$.

8. ($h$)  
   ​

   $(A\cap B)C\subseteq AC\cap BC$ i $A(B\cap C)\subseteq AB\cap AC$.

9. ($i$)  
   ​

   $(A\cap B)C\supseteq AC\cap BC$ i $A(B\cap C)\supseteq AB\cap AC$.

Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general.

1. ($a$)  
   ​

   $L^{*}=\{a,b\}^{*}\;\Rightarrow\;\{a,b\}\subseteq L$.

2. ($b$)  
   ​

   $L_{1}^{*}L_{2}^{*}\subseteq(L_{1}L_{2})^{*}$.

3. ($c$)  
   ​

   $L_{1}^{*}L_{2}^{*}\supseteq(L_{1}L_{2})^{*}$.

4. ($d$)  
   ​

   $L_{1}^{+}\cup L_{2}^{+}=\{a,b\}^{+}\;\wedge\;L_{1}^{+}\cap L_{2}^{+}=\emptyset\;\Rightarrow\;L_{1}=\emptyset\;\vee\;L_{2}=\emptyset$.

5. ($e$)  
   ​

   $(L_{1}^{*}\cup L_{2}^{*})\subseteq(L_{1}\cup L_{2})^{*}$.

6. ($f$)  
   ​

   $(L_{1}^{*}\cup L_{2}^{*})\supseteq(L_{1}\cup L_{2})^{*}$.

7. ($g$)  
   ​

   $(L_{1}\cap L_{2})^{*}\subseteq(L_{1}^{*}\cap L_{2}^{*})$.

8. ($h$)  
   ​

   $(L_{1}\cap L_{2})^{*}\supseteq(L_{1}^{*}\cap L_{2}^{*})$.

9. ($i$)  
   ​

   $L_{1}^{*}\subseteq L_{2}^{*}\;\Rightarrow\;L_{1}\subseteq L_{2}$.

10. ($j$)  
    ​

    $\overline{L^{*}}\subseteq\overline{L}\subseteq\overline{L}^{*}$.

11. ($k$)  
    ​

    $\overline{L^{*}}\supseteq\overline{L}\supseteq\overline{L}^{*}$.

12. ($l$)  
    ​

    $L_{1}\not=\emptyset\;\wedge\;L_{2}\not=\emptyset\;\wedge\;L_{1}\cap L_{2}=\emptyset\;\Rightarrow\;L_{1}^{*}\not=L_{2}^{*}$.

13. ($m$)  
    ​

    $L^{+}L^{+}\subseteq L^{+}$.

14. ($n$)  
    ​

    $L^{+}L^{+}\supseteq L^{+}$.

15. ($o$)  
    ​

    $(L^{2})^{*}\subseteq(L^{*})^{2}$.

16. ($p$)  
    ​

    $(L^{2})^{*}\supseteq(L^{*})^{2}$.

17. ($q$)  
    ​

    $L\subseteq L^{2}\Leftrightarrow(\lambda\in L)\vee(L=\emptyset)$.

18. ($r$)  
    ​

    $L^{2}\subseteq L\Leftrightarrow L=L^{+}$.

19. ($s$)  
    ​

    $(\lambda\in L)\wedge(L^{2}\subseteq L)\Leftrightarrow L=L^{*}$.

20. ($t$)  
    ​

    $L=L^{2}\Rightarrow(L=L^{*})\vee(L=\emptyset)$.

Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general.

1. ($a$)  
   ​

   $(xy)^{R}=y^{R}x^{R}$.

2. ($b$)  
   ​

   $(L_{1}L_{2})^{R}=L_{2}^{R}L_{1}^{R}$.

3. ($c$)  
   ​

   $(L_{1}\cup L_{2})^{R}=L_{1}^{R}\cup L_{2}^{R}$.

4. ($d$)  
   ​

   $(L_{1}\cap L_{2})^{R}=L_{1}^{R}\cap L_{2}^{R}$.

5. ($e$)  
   ​

   $\overline{L}^{R}=\overline{L^{R}}$.

6. ($f$)  
   ​

   $(L^{*})^{R}=(L^{R})^{*}$.

7. ($g$)  
   ​

   $(L_{1}L_{2})^{R}=L_{1}^{R}L_{2}^{R}\;\Rightarrow\;L_{1}=L_{2}$.

Quines de les següents definicions de la funció $\sigma$ defineixen un morfisme (és a dir, cumpleixen $\sigma(xy)=\sigma(x)\sigma(y)$ per a mots $x,y$ qualssevol).

1. ($a$)  
   ​

   $\sigma(a_{1}a_{2}\cdots a_{n})=a_{1}a_{1}a_{2}a_{2}\cdots a_{n}a_{n}$, essent $a_{1},\ldots,a_{n}$, tot ells, símbols de l’alfabet.

2. ($b$)  
   ​

   $\sigma(a_{1}a_{2}a_{3}\cdots a_{n})=a_{1}a_{2}a_{2}a_{3}a_{3}a_{3}\cdots\overbrace{a_{n}\cdots a_{n}}^{n)}$, essent $a_{1},\ldots,a_{n}$, tot ells, símbols de l’alfabet.

3. ($c$)  
   ​

   $\sigma(w)=w$.

4. ($d$)  
   ​

   $\sigma(w)=\lambda$.

5. ($e$)  
   ​

   $\sigma(w)=a^{|w|}$.

6. ($f$)  
   ​

   $\sigma(w)=w^{R}$.

7. ($g$)  
   ​

   $\sigma(w)=\sigma_{1}(\sigma_{2}(w))$ per a morfismes $\sigma_{1},\sigma_{2}$.

Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general, on $\sigma$ és un morfisme.

1. ($a$)  
   ​

   $\sigma(L_{1}L_{2})=\sigma(L_{1})\sigma(L_{2})$.

2. ($b$)  
   ​

   $\sigma(L^{n})=\sigma(L)^{n}$.

3. ($c$)  
   ​

   $\sigma(L_{1}\cup L_{2})=\sigma(L_{1})\cup\sigma(L_{2})$.

4. ($d$)  
   ​

   $\sigma(L^{*})=\sigma(L)^{*}$.

5. ($e$)  
   ​

   $\sigma(L^{R})=\sigma(L)^{R}$.

6. ($f$)  
   ​

   $\sigma(\overline{L})=\overline{\sigma(L)}$.

7. ($g$)  
   ​

   $\sigma(L)=L\;\Rightarrow\;\forall x\in L:\sigma(x)=x$.

Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general.

1. ($a$)  
   ​

   $|L_{1}|\cdot|L_{2}|=|L_{1}\cdot L_{2}|$.

2. ($b$)  
   ​

   $(\forall a,b\in\Sigma:(a\not=b\Rightarrow\sigma(a)\not=\sigma(b)))\Rightarrow|\sigma(L)|=|L|$, on $\sigma$ és un morfisme.

3. ($c$)  
   ​

   $|L^{R}|=|L|$.

4. ($d$)  
   ​

   $|L^{n}|=|L|^{n}$.

Donat un llenguatge $L$, shiftar $L$ dóna lloc a un nou llenguatge, que denotem $S(L)$, i que conté als mots que s’obtenen agafant cada mot de $L$ i rotant-lo de totes les maneres possibles, formalment: $S(L)=\{vu\mid uv\in L\}$. Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general.

1. ($a$)  
   ​

   $S(L)^{*}\subseteq S(L^{*})$.

2. ($b$)  
   ​

   $S(L)^{*}\supseteq S(L^{*})$.

3. ($c$)  
   ​

   $\overline{S(L)}=S(\overline{L})$.

4. ($d$)  
   ​

   $S(L^{R})=S(L)^{R}$.

5. ($e$)  
   ​

   $S(L_{1}\cup L_{2})=S(L_{1})\cup S(L_{2})$.

6. ($f$)  
   ​

   $S(L_{1}\cap L_{2})=S(L_{1})\cap S(L_{2})$.

7. ($g$)  
   ​

   $S(L_{1}L_{2})=S(L_{1})S(L_{2})$.

8. ($h$)  
   ​

   $S(\sigma(L))=\sigma(S(L))$, on $\sigma$ és un morfisme.

Demostreu que no hi ha cap mot $w$ que satisfaci $aw=wb$, essent $a$ i $b$ símbols de l’alfabet.

Demostreu que, per a qualsevol alfabet $\Sigma$, hi ha un únic llenguatge $L$ que satisfà $L=\overline{\Sigma L}$. Quin és aquest llenguatge?