Exercici 1 (De descripcions informals a formals) Donat un alfabet \Sigma, sovint es poden descriure llenguatges interessants L\subseteq \Sigma^* utilitzant la notació de conjunts L=\{w\in \Sigma^* \mid P(w)\}, on P(w) és un predicat (P) definit sobre un mot w. Per exemple, el llenguatge L de tots els mots sobre \{a,b\} que contenen el submot ab es pot descriure com
L=\{w\in \{a,b\}^* \mid \exists x,y\in \{a,b\}^*\ w=xaby\}.
Descriviu els llenguatges formal sobre \Sigma=\{a,b\} per les descripcions informals següents de P(w):
A la dreta de cada submot ab de w hi ha algun submot ba.
El mot w conté el submot ab i el submot ba.
Entre cada dues b’s hi ha alguna a.
Tota ocurrència de b és en posició parella (el primer símbol d’un mot ocupa la posició 1).
El mot w té algun prefix amb almenys tantes b’s com a’s.
En cada prefix de w hi ha almenys tantes b’s com a’s.
El mot w té algun prefix de mida parella amb almenys tantes b’s com a’s.
Tot prefix de w de mida parella té almenys tantes b’s com a’s.
El mot w té un prefix i un sufix idèntics i no buits de mida més petita que la del mateix mot.
El mot w és un palíndrom, és a dir, es llegeix igual d’esquerra a dreta com de dreta a esquerra, com ara tot o anilina en català.
Exercici 2 (Concatenació — propietats bàsiques) Justifiqueu les vostres respostes a les preguntes següents. Els mots i els llenguatges corresponen a un alfabet fixat.
És la concatenació commutativa? Es compleix que xy=yx per tots els mots x,y? Es compleix que AB=BA per tots els llenguatges A,B? Depenen les respostes anteriors de la mida de l’alfabet?
És la concatenació de llenguatges associativa? Es compleix que x(yz)=(xy)z per tots els mots x,y,z? Es compleix A(BC)=(AB)C per tots els llenguatges A,B,C? Depenen les respostes anteriors de la mida de l’alfabet?
Es compleix la llei de cancel·lació per la concatenació de mots? És a dir, es compleix que xy=xz implica y=z per tots els mots x,y,z?
Es compleix la llei de cancel·lació per la concatenació de llenguatges? És a dir, es compleix que AB=AC implica B=C per tots els llenguatges A,B,C? I si addicionalment imposem que A\neq \emptyset, es compleix ara?
Condició per una doble igualtat. Donats quatre llenguatges A,B,C,D tals que A,B són no buits, AB=CD i tots els mots a A i C tenen la mateixa mida, es compleix que A=C and B=D?
Distribueix la concatenació de llenguatges sobre la reunió? És a dir, es compleix que (A\cup B) C=AC\cup BC i A(B\cup C)=AB\cup AC per tots els llenguatges A,B,C? I si en lloc de “=” només demanem “\subseteq” o “\supseteq”, es compleix ara?
Distribueix la concatenació de llenguatges sobre la intersecció? És a dir, es compleix que (A\cap B) C=AC\cap BC i A(B\cap C)=AB\cap AC per tots els llenguatges A,B,C? I si en lloc de “=” només demanem “\subseteq” o “\supseteq”, es compleix ara?
Exercici 3 (Estrella de Kleene — propietats bàsiques) Justifiqueu les vostres respostes a les preguntes següents. Els llenguatges estan definits sobre un alfabet fixat qualsevol.
Distribueix l’estrella de Kleene sobre la concatenació de llenguatges? És a dir, per tot parell de llenguatges L_1,L_2, es compleix que L_1^*L_2^*= (L_1L_2)^*? I si en lloc de “=” només es demana “\subseteq” o “\supseteq”? I si imposem L_1=L_2, es compleix ara? I si quan L_1=L_2, en lloc de “=” només es demana per “\subseteq” o “\supseteq”?
Indueixen sempre les clausures positives particions no trivials? És a dir, per tot parell de llenguatges L_1,L_2, si L_1^+\cup L_2^+=\{a,b\}^+ i L_1^+\cap L_2^+=\emptyset, llavors o bé L_1=\emptyset o bé L_2=\emptyset.
Distribueix l’estrella de Kleene sobre la reunió de llenguatges? És a dir, per tot parell de llenguatges L_1,L_2, es compleix que L_1^*\cup L_2^*= (L_1\cup L_2)^*? I si en lloc de “=” només es demana “\subseteq” o “\supseteq”?
Distribueix l’estrella de Kleene sobre la intersecció de llenguatges? És a dir, per tot parell de llenguatges L_1,L_2, es compleix que L_1^*\cap L_2^*= (L_1\cap L_2)^*? I si en lloc de “=” només es demana “\subseteq” o “\supseteq”?
És l’estrella de Kleene monòtona respecte de la inclusió? És a dir, per tot parell de llenguatges L_1,L_2, L_1\subseteq L_2 implica L_1^*\subseteq L_2^*? Es compleix la recíproca? És a dir, per tot parell de llenguatges L_1,L_2, L_1^*\subseteq L_2^* implica L_1\subseteq L_2? I si L_1=\{a,b\} i L_2 és un llenguatge sobre \{a,b\}, es compleix la recíproca en aquest context especial?
Cadena d’inclusions. Es compleix per tot llenguatge L que \overline{L^*}\subseteq \overline{L}\subseteq \overline{L}^*? I si capgirem les inclusions? Es compleix \overline{L^*}\supseteq \overline{L}\supseteq \overline{L}^*?
Condició suficient per estrelles de Kleene diferents. Donats dos llenguatges L_1, L_2 \not=\emptyset qualssevol, es compleix que L_1\cap L_2=\emptyset implica L_1^*\not=L_2^*?
On és el tancament positiu al quadrat? Es compleix L^+L^+\subseteq L^+ per tot llenguatge L? Es compleix la inclusió inversa L^+L^+\supseteq L^+?
Exercici 4 (Caracteritzacions) Justifiqueu les vostres respostes a les preguntes següents. Els llenguatges estan definits sobre un alfabet fixat qualsevol.
Quan és un llenguatge igual al seu tancament positiu? Es compleix L=L^+ si i només si L^2 \subseteq L?
Quan és un llenguatge igual a la seva estrella de Kleene? És L^2\subseteq L una condició necessària per la igualtat L= L^*? És \lambda \in L una condició necessària per L= L^*? Quina combinació lògica (\land, \lor, …) de les afirmacions L^2\subseteq L i \lambda\in L constitueix una condició necessària i suficient per la igualtat L= L^*?
Quan està un llenguatge inclòs en el seu quadrat? És \lambda\in L una condició suficient per la inclusió L\subseteq L^2? És L = \emptyset una condició suficient per L\subseteq L^2? Quina combinació lògica (\land, \lor, …) de les afirmacions L = \emptyset i \lambda\in L constitueix una condició suficient i necessària per la inclusió L\subseteq L^2?
Quan és un llenguatge igual al seu quadrat? És L=L^* una condició suficient per la igualtat L= L^2? És L = \emptyset una condició suficient per L= L^2? Quina combinació lògica (\land, \lor, …) de les afirmacions L = L^* i L=\emptyset constitueix una condició suficient i necessària per la igualtat L = L^2?
Exercici 5 (Revessat – propietats bàsiques) Justifiqueu les respostes a les preguntes següents.
El revessat de la concatenació (1). Demostreu que per tot parell de mots x,y, (xy)^R=y^Rx^R. Es compleix la propietat anàloga per llenguatges? És a dir, donats dos llenguatges L_1,L_2, es compleix que (L_1L_2)^R=L_2^RL_1^R?
El revessat de la concatenació (2). És veritat que, donats dos llenguatges L_1,L_2 tals que (L_1L_2)^R=L_1^R L_2^R, es compleix L_1=L_2 necessàriament?
Distribueix el revessat sobre la reunió? És a dir, donats llenguatges L_1,L_2, es compleix que (L_1\cup L_2)^R=L_1^R\cup L_2^R?
Distribueix el revessat sobre la intersecció? És a dir, donats llenguatges L_1,L_2, es compleix que (L_1\cap L_2)^R=L_1^R\cap L_2^R?
Commuten el complementari i el revessat de llenguatges? És a dir, és cert que \overline{L}^R=\overline{L^R}?
Commuten l’estrella de Kleene i el revessat d’un llenguatge? És a dir, és cert que (L^*)^R=(L^R)^*?
Exercici 6 (Homomorfismes I – propietats bàsiques) Sigui \sigma :\Sigma^* \to \Sigma^* una funció. Quines de les definicions següents de \sigma defineix un homomorfisme? És a dir, quines satisfan que per mots x,y\in \Sigma^* qualssevol, \sigma(xy)=\sigma(x)\sigma(y)? Sigui w=a_1a_2\cdots a_n \in \Sigma^*, on a_1,a_2,\dots, a_n \in \Sigma.
\sigma(w)=a_1a_1a_2a_2\cdots a_na_n.
\sigma(w)=a_1a_2a_2a_3a_3a_3\cdots\overbrace{a_n\cdots a_n}^{n)}.
\sigma(w)=ww.
\sigma(w)=w.
\sigma(w)=\lambda.
\sigma(w)=a^{|w|}, on a\in \Sigma.
\sigma(w)=w^R.
\sigma(w)=\sigma_1(\sigma_2(w)), on \sigma_1,\sigma_2 són homomorfismes.
Exercici 7 (Homomorfismes II – propietats bàsiques) Donat un homomorfisme \sigma:\Sigma^*\to\Sigma^* i llenguatges L,L_1,L_2\subseteq \Sigma^*, justifiqueu les vostres respostes a les preguntes següents.
Distribueix l’homomorfisme de llenguatges sobre la concatenació? És a dir, es compleix \sigma(L_1L_2)=\sigma(L_1)\sigma(L_2)?
Commuten l’homomorfisme i l’exponenciació de llenguatges? És a dir, es compleix \sigma(L^n)=\sigma(L)^n per qualsevol natural n?
Commuten l’homomorfisme i la reunió de llenguatges? És a dir, es compleix \sigma(L_1\cup L_2)= \sigma(L_1)\cup\sigma(L_2)?
Commuten l’homomorfisme de llenguatges i l’estrella de Kleene? És a dir, es compleix \sigma(L^*)=\sigma(L)^*?
Commuten l’homomorfisme i el revessat de llenguatges? És a dir, es compleix \sigma(L^R)=\sigma(L)^R?
Commuten l’homomorfisme i la complementació de llenguatges? És a dir, es compleix \sigma(\overline{L})=\overline{\sigma(L)}?
Actua l’homomorfisme identitat sobre un llenguatge com la identitat sobre els seus mots? És a dir, es compleix \sigma(x)=x per a tot x a L si \sigma(L)=L?
Exercici 8 (Sobre la mida dels llenguatges) Justifiqueu les respostes a les preguntes següents.
Donats dos llenguatges L_1,L_2, és cert que |L_1|\cdot|L_2|=|L_1\cdot L_2|? I si L_1=L_2?
Donat un homomorfisme \sigma, és cert que si \sigma és injectiu, llavors |\sigma(L)|=|L|?
Donat un llenguatge L, és cert que |L^R|=|L|?
Donat un llenguatge L i un natural n, és cert que |L^n|=|L|^n?
Exercici 9 (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.
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 homomorfisme.
Exercici 10 (Simplificació de llenguatges) Demostreu les igualtats següents entre llenguatges:
\{w\in \{a,b\}^* \mid aw=wb\}=\emptyset.
\{w\in \{a,b\}^* \mid abw=wab\}=\{ab\}^*.
Alerta\{ab\}^* no és un lapsus, no hi ha “,” entre a i b.
\{xy\in \{a,b\}^* \mid |x|_a=|y|_a\}=\{w\in \{a,b\}^*\mid |w|_a\in 2\mathbb N\}.
\{xy\in \{a,b\}^* \mid |x|_a=|y|_b\}=\{a,b\}^*.
\{xy\in \{a,b\}^* \mid |x|_{aa}=|y|_b\}=\{a,b\}^*.
\{w\in \{0,1\}^* \mid \mathtt{value}_2(ww^R)\in 3\mathbb N\}=\{0,1\}^*
Exercici 11 (L=\overline{\Sigma L}) Demostreu que, per a qualsevol alfabet \Sigma, hi ha un únic llenguatge L que satisfà L=\overline{\Sigma L}. Quin és aquest llenguatge?
Doneu una expressió alternativa per a L. Conté L el mot buit \lambda? Si un mot de L és de la forma aw, amb a pertanyent a \Sigma, on pertany w? A L o a \overline L? Un cop obtingueu la nova expressió, deixeu-la en funció de L i resolgueu la recurrència.
Exercici 12 (Passejades arbitràriament llargues en grafs) Donat un graf dirigit G (amb bucles) de n vèrtexs i dos vèrtexs seus s, t, demostreu que si existeix una passejada a G de s a t de mida > n, llavors hi ha passejades arbitràriament llargues de s a t. En altres paraules, que existeix un n_0\in \mathbb N tal que per tot m\geq n_0 hi ha una passejada a G de s a t de mida \geq m.
Exercici 13 (Inducció senzilla) Sigui f: {\mathbb N} \rightarrow \mathbb N una funció tal que f(x+y) = f(x)+f(y) per x, y \in \mathbb N. Demostreu que per qualsevol x \in \mathbb N, f(x) = f(1) \cdot x.
Exercici 14 (Divisibilitat en un conjunt de nombres) Demostreu que tot conjunt de n+1 naturals més petits o iguals que 2n, on n \ge 1, conté dos elements diferents a i b tals que a divideix b.
Una possibilitat és fer servir el principi de les caselles: les cartes són els n+1 nombres i les caselles són els nombres senars entre 1 i 2n. Una carta de la forma 2^k d amb d senar es diposita en la casella d.
Una altra opció és considerar una demostració per inducció en n i distingir dos casos en el pas d’inducció: almenys un dels elements 2n+1 i 2n+2 no és al conjunt o tots dos hi són.