Ejercicios para la evaluación continua
Tema 1: Teoría de Lenguajes
Ejercicio 1 Formalitzeu els següents llenguatges utilitzant la notació clàssica de conjunts, com a parell variable de mot (w\in \Sigma^*) i propietat (P) definida sobre mots, de manera que el llenguatge es pot definir com el conjunt \{w \in \Sigma^* \mid P(w)\}. Per a definir formalment la propietat P feu servir quantificadors universals i existencials (\forall,\exists), operadors booleans (\lor, \land, \implies, …) i les notacions sobre mides de mots que hem introduït.
Llenguatge dels mots sobre \{a,b\} que contenen el submot ab.
Llenguatge dels mots sobre \{a,b\} tals que a la dreta de cada submot ab hi ha algun submot ba.
Llenguatge dels mots sobre \{a,b\} que contenen el submot ab i el submot ba.
Llenguatge dels mots sobre \{a,b,c\} tals que entre cada dues b’s hi ha alguna a.
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).
Llenguatge dels mots sobre \{a,b\} amb algun prefix amb més b’s o igual que a’s.
Llenguatge dels mots sobre \{a,b\} tals que qualsevol prefixe seu té més b’s o igual que a’s.
Llenguatge dels mots sobre \{a,b\} amb algun prefix de mida parell amb més b’s o igual que a’s.
Llenguatge dels mots sobre \{a,b\} tals que qualsevol prefixe seu de mida parell té més b’s o igual que a’s.
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.
Ejercicio 2 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.
xy=yx.
xy=xz\implies y=z.
A(BC)=(AB)C.
AB=BA.
A\not=\emptyset \land AB=AC \implies B=C.
A\not=\emptyset \land B\not=\emptyset \land AB=CD \land (\forall u\in A,v\in C:|u|=|v|) \implies A=C \land B=D.
(A\cup B) C=AC\cup BC i A(B\cup C)=AB\cup AC.
(A\cap B) C\subseteq AC\cap BC i A(B\cap C)\subseteq AB\cap AC.
(A\cap B) C\supseteq AC\cap BC i A(B\cap C)\supseteq AB\cap AC.
Ejercicio 3 (Estrella de Kleene) Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general.
L^*=\{a,b\}^* \implies \{a,b\}\subseteq L.
L_1^*L_2^*\subseteq (L_1L_2)^*.
L_1^*L_2^*\supseteq (L_1L_2)^*.
L_1^+\cup L_2^+=\{a,b\}^+ \land L_1^+\cap L_2^+=\emptyset \implies L_1=\emptyset \lor L_2=\emptyset.
(L_1^*\cup L_2^*)\subseteq (L_1\cup L_2)^*.
(L_1^*\cup L_2^*)\supseteq (L_1\cup L_2)^*.
(L_1\cap L_2)^*\subseteq (L_1^*\cap L_2^*).
(L_1\cap L_2)^*\supseteq (L_1^*\cap L_2^*).
L_1^*\subseteq L_2^* \implies L_1\subseteq L_2.
\overline{L^*}\subseteq \overline{L}\subseteq \overline{L}^*.
\overline{L^*}\supseteq \overline{L}\supseteq \overline{L}^*.
L_1\not=\emptyset \land L_2\not=\emptyset \land L_1\cap L_2=\emptyset \implies L_1^*\not=L_2^*.
L^+L^+\subseteq L^+.
L^+L^+\supseteq L^+.
(L^2)^*\subseteq (L^*)^2.
(L^2)^*\supseteq (L^*)^2.
L\subseteq L^2\iff (\lambda\in L) \lor (L=\emptyset).
L^2\subseteq L\Leftrightarrow L=L^+.
(\lambda\in L) \land (L^2\subseteq L) \iff L=L^*.
L=L^2 \implies (L=L^*) \lor (L=\emptyset).
Ejercicio 4 (Reverso) Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general.
(xy)^R=y^Rx^R.
(L_1L_2)^R=L_2^RL_1^R.
(L_1\cup L_2)^R=L_1^R\cup L_2^R.
(L_1\cap L_2)^R=L_1^R\cap L_2^R.
\overline{L}^R=\overline{L^R}.
(L^*)^R=(L^R)^*.
(L_1L_2)^R=L_1^R L_2^R \implies L_1=L_2.
Ejercicio 5 (Morfismos I) 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).
- \sigma(a_1a_2\cdots a_n)=a_1a_1a_2a_2\cdots a_na_n, essent a_1, \ldots, a_n, tot ells, símbols de l’alfabet.
- \sigma(a_1a_2a_3\cdots a_n)=a_1a_2a_2a_3a_3a_3\cdots\overbrace{a_n\cdots a_n}^{n)}, essent a_1, \ldots, a_n, tot ells, símbols de l’alfabet.
- \sigma(w)=w.
- \sigma(w)=\lambda.
- \sigma(w)=a^{|w|}.
- \sigma(w)=w^R.
- \sigma(w)=\sigma_1(\sigma_2(w)) per a morfismes \sigma_1,\sigma_2.
Ejercicio 6 (Morfismos II) Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general, on \sigma és un morfisme.
- \sigma(L_1L_2)=\sigma(L_1)\sigma(L_2).
- \sigma(L^n)=\sigma(L)^n.
- \sigma(L_1\cup L_2)= \sigma(L_1)\cup\sigma(L_2).
- \sigma(L^*)=\sigma(L)^*.
- \sigma(L^R)=\sigma(L)^R.
- \sigma(\overline{L})=\overline{\sigma(L)}.
- \sigma(L)=L \implies \forall x\in L:\sigma(x)=x.
Ejercicio 7 Argumenteu si són certes (amb una justificació) o falses (amb un contraexemple) les següents afirmacions en general.
- |L_1|\cdot|L_2|=|L_1\cdot L_2|.
- (\forall a,b\in\Sigma:(a\not=b\implies \sigma(a)\not=\sigma(b)))\implies |\sigma(L)|=|L|, on \sigma és un morfisme.
- |L^R|=|L|.
- |L^n|=|L|^n.
Ejercicio 8 (Shiftar) 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.
- S(L)^*\subseteq S(L^*).
- S(L)^*\supseteq S(L^*).
- \overline{S(L)}=S(\overline{L}).
- S(L^R)=S(L)^R.
- S(L_1\cup L_2)=S(L_1)\cup S(L_2).
- S(L_1\cap L_2)=S(L_1)\cap S(L_2).
- S(L_1L_2)=S(L_1)S(L_2).
- S(\sigma(L))=\sigma(S(L)), on \sigma és un morfisme.
Ejercicio 9 Demostreu que no hi ha cap mot w que satisfaci aw=wb, essent a i b símbols de l’alfabet.
Ejercicio 10 Demostreu que, per a qualsevol alfabet \Sigma, hi ha un únic llenguatge L que satisfà L=\overline{\Sigma L}. Quin és aquest llenguatge?