Llista de problemes 1

Intruccions

Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:

Vídeos de G. Godoy

• Autómatas finitos deterministas
• Autómatas finitos indeterministas
• Notacions de DFAs i NFAs (1)
• Notacions de DFAs i NFAs (2)
• Operacions sobre Reg (1)
• Operacions sobre Reg (2)
• Operacions sobre Reg (3)
• Minimització de DFAs (1)
• Minimització de DFAs (2)
• Minimització de DFAs (3)

Llibres

• Exemples de construcció d’autòmats finits (Lluís Màrquez, Enrique Romero)
• (Cases i Màrquez 2003, \S 4 and \S 5)
• (Sipser 2013, \S 1.1 and \S 1.2)
• (Hopcroft, Motwani, i Ullman 2007, \S 2.1, \S 2.2 and \S 4.2)

Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. Edicions UPC.

Hopcroft, John E., Rajeev Motwani, i Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.

Sipser, Michael. 2013. Introduction to the theory of computation. 3rd edition. Cengage Learning.

Tots els exercicis

Exercici 1 (Unió i intersecció de llenguatges regulars – la construcció del producte) Donat un mot w\in \{a,b\}^*, sigui L_w=\{xwy\mid x,y\in\{a,b\}^*\}. En altres paraules, L_w és el llenguatge dels mots que contenen w com a submot.

1. Demostreu que per tot mot w, L_w és un llenguatge regular.

2. Construïu DFAs mínims que reconeguin els llenguatges següents. Demostreu que els DFAs construïts són correctes i tenen el nombre més petit possible d’estats.

   • L_{a}
   • L_{aa}
   • L_{aaa}

3. Fent servir la construcció del producte cartesià, contruïu DFAs que reconeguin els llenguatges següents i minimitzeu els DFAs obtinguts.

   • L_{aa}\cup L_{bb}
   • L_{a}\cup L_{bbb}

   Què canviaria en cas de voler els llenguatges L_{aa}\cap L_{bb} and L_{a}\cap L_{bbb}?

4. Donats dos DFAs A i B com a entrada, quin és el cost de calcular un DFA per L(A)\cup L(B) i L(A)\cap L(B) fent servir la construcció del producte cartesià?

5. Donats DFAs mínims A i B, és el DFA que reconeix L(A)\cup L(B) obtingut amb la construcció del producte d’A i B mínim? Què es pot dir del DFA per L(A)\cap L(B)?

6. Què passa si apliquem la construcció del producte cartesià a NFAs en lloc de DFAs? Dona també la construcció del producte de NFAs un bon NFA per la unió (resp. intersecció)?

Exercici 2 (El complementari d’un llenguatge regular és regular) Intercanviar estats finals i no finals en un DFA A produeix un nou DFA que reconeix el complementari del llenguatge reconegut per A.

1. Demostreu que L=\{aax\mid x\in\{a,b\}^*\} és un llenguatge regular. Construïu els DFAs mínims que reconeixen L i \overline{L}.

2. Demostreu que L=\{w \in \{a,b\}^* \mid |w|\in 3\mathbb N +1\} és un llenguatge regular. Construïu els DFAs mínims que reconeixen L i \overline{L}.

3. Demostreu que L=\{w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 3\mathbb N\} és un llenguatge regular. Construïu els DFAs mínims que reconeixen L i \overline{L}.

4. Donat un DFA A com a entrada, quin és el cost de calcular un DFA per \overline{L(A)}?

5. Si partíssim d’un DFA mínim, seria mínim el DFA obtingut per al complement?

6. Intercanviar estats finals i no finals en un NFA A produeix un NFA que reconeix el complement del llenguatge reconegut per A?

Exercici 3 (La concatenació de llenguatges regulars és regular)  

1. Construeix el DFA mínim per al llenguatge L_1\cdot L_2, on

   1. L_1=\{xaya\mid x,y\in\{a,b\}^*\} i L_2=\{bxby\mid x,y\in\{a,b\}^*\}.
   2. L_1=\{xaay\mid x,y\in\{a,b\}^*\} i L_2=\{bxb\mid x\in\{a,b\}^*\}.
   3. L_1=\{xaya\mid x,y\in\{a,b\}^*\} i L_2=\{bxb\mid x\in\{a,b\}^*\}.

   Trobeu els DFAs mínims que reconeixen L_1 i L_2. A partir d’ells, construïu un \lambda-NFA A que reconegui el llenguatge. Finalment, fent servir la construció de subconjunts, feu A determinista i minimitzeu el DFA obtingut.

2. Donats dos DFAs A i B com a entrada, quin és el cost de construir un DFA per a L(A) \cdot L(B)?

Exercici 4 (L’estrella de Kleene d’un llenguatge regular és regular)  

1. Construïu de forma explícita el DFA mínim per al llenguatge L^*, on

   1. L=\{xay\in\{a,b\}^*\mid |y|=1\}.
   2. L=\{xaby\in\{a,b\}^*\mid |y|=1\}.
   3. L=\{axaby\in\{a,b\}^*\mid |y|=1\}.

   Construïu el mínim DFA que reconeix L. A partir d’aquí, construïu un \lambda-NFA A que reconegui el llenguatge L^*. Fent servir la construcció del conjunt de parts, determinitzeu A i, finalment, minimitzeu el DFA obtingut.

2. Donat un DFA A com a entrada, quin és el cost de construir un DFA per a L(A)^*?

Exercici 5 (El revessat d’un llenguatge regular és regular)  

1. Construïu de forma explícita el DFA mínim per al llenguatge L^R, on

   1. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|_b\in 2\mathbb N )\}.
   2. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|_b\in 2\mathbb N +1)\}.
   3. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|\in 2\mathbb N )\}.

   Construïu el DFA mínim que reconeix L. A partir d’aquí, construïu un NFA A que reconegui el llenguatge L^R. Fent servir la construcció del conjunt de parts, determinitzeu A i finalment minimitzeu el DFA obtingut.

2. Donat un DFA A com a entrada, quin és el cost de construir un DFA per a L(A)^R?

3. Revessar la direcció de les transicions i intercanviar estats inicials i finals en un DFA A produeix un NFA B per a L(A)^R. Si l’NFA obtingut és de fet un DFA i A és mínim, és B mínim?

4. Un NFA és d’acceptació única si per tot mot existeix una única execució acceptadora. Demostreu que, per a un NFA A d’acceptació única, l’NFA A^R és d’acceptació única.

Exercici 6 (L’homomorfisme d’un llenguatge regular és regular)  

1. Construïu de forma explícita el DFA mínim per al llenguatge \sigma(L), on

   1. L=\{axbya\mid x,y\in\{a,b\}^*\} i \sigma és l’homomorfisme definit per \sigma(a)=aa i \sigma(b)=ba.
   2. L=\{axbyc\mid x,y\in\{a,b,c\}^*\} i \sigma és l’homomorfisme definit per \sigma(a)=ab, \sigma(b)=b i \sigma(c)=\lambda.
   3. L=\{xbcya\mid x,y\in\{a,b,c\}^*\} i \sigma és l’homomorfisme definit per \sigma(a)=bbb, \sigma(b)=a i \sigma(c)=\lambda.

   Calculeu el DFA mínim que reconeix L. A partir d’aquest DFA, construïu el \lambda-NFA A que reconeix el llenguatge \sigma(L). Finalment, fent servir la construcció de subconjunts, feu A determinista i minimitzeu el DFA obtingut.

   Recordeu que, donat un DFA A i un morfisme \sigma, és possible construir un NFA que reconegui el llenguatge \sigma(L(A)) transformant cada transició \ \stackrel{a}{\to}\ a A en \ \stackrel{\sigma(a)}{\to}\ en un autòmat estès i convertint cada transició estesa en un \lambda-NFA tot afegint nous estats.

2. Donat un DFA A com a entrada, quin és el cost de calcular un DFA per a \sigma(L(A))? Produeix un DFA la construcció per obtenir un NFA que reconegui \sigma(L(A))?

3. Funciona la construcció per obtenir un NFA que reconegui \sigma(L(A)) en cas que A sigui un NFA? En altres paraules, si es transforma cada transició \ \stackrel{a}{\to}\ d’un NFA A en una transició estesa \ \stackrel{\sigma(a)}{\to}\ i després es converteix en un \lambda-NFA tot afegint nous estats, s’obté un \lambda-NFA correcte per a \sigma(L(A))?

Exercici 7 (L’homomorfisme invers d’un llenguatge regular és regular)  

1. Demostreu que L=\{w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 3 \mathbb N\} és un llenguatge regular. Calculeu de forma explícita el DFA mínim per al llenguatge \sigma^{-1}(L), on \sigma: \{a,b,c\}\to \{0,1\} és l’homomorfirme definit per

   1. \sigma(a)=01,
      \sigma(b)=0 i
      \sigma(c)=\lambda.
   2. \sigma(a)=10,
      \sigma(b)=0 i
      \sigma(c)=\lambda.
   3. \sigma(a)=00,
      \sigma(b)=11 i
      \sigma(c)=\lambda.
   4. \sigma(a)=001,
      \sigma(b)=101 i
      \sigma(c)=0.
   Recordeu que, donat un DFA A i un morfisme \sigma, és possible construir un DFA A' que reconegui el llenguatge \sigma^{-1}(L(A)) de la manera següent: amb entrada w, A' executa A sobre entrada \sigma(w) i accepta si ho fa A.

2. Donat un DFA A i un homomorfisme \sigma, quin és el cost de construir un DFA per al llenguatge \sigma^{-1}(L(A))?

3. Suposeu que es construeix un DFA per a \sigma^{-1}(L(A)) partint d’un DFA A mínim. És també mínim el DFA resultant?

4. Funciona també la construcció usada per obtenir el DFA per a \sigma^{-1}(L(A)) en cas que A sigui un NFA?

Exercici 8 (Minimització de DFAs)  

1. Un DFA amb estats inaccessibles no pot ser mínim. Quin és el cost de determinar si un DFA té estats inaccessibles?

2. Quin és el cost de l’algorisme de minimització de Moore (amb una implementació raonable)?

3. El mínim DFA que reconeix un llenguatge donat és únic llevat d’isomorfismes. Què es pot dir dels NFAs? En concret, és un NFA de mida mínima únic per un llenguatge donat?

Exercici 9 (Els NFAs poden ser exponencialment més succints que els DFAs) Donat un n\in \mathbb N, considereu el llenguatge L_n = \{ xay \mid x,y \in \{a,b\}^* \land |y| = n\}.

1. Quin és el cost de l’algorisme de determinització (en funció de la mida de l’NFA d’entrada)?

2. Demostreu que L_n és regular construïnt un NFA que reconeix L_n amb n+2 estats.

3. Demostreu que el DFA mínim que reconeix L_n té 2^{n+1} estats. És a dir,

   1. demostreu que existeix un DFA que reconeix L_n amb 2^{n+1} states i
   2. demostreu que cap DFA amb menys de 2^{n+1} estats pot reconèixer L_n.

Recordeu que la notació compacta usada en la definició de L_n correspon al llenguatge \{ w \in \{a,b\}^* \mid \exists x,y\ (w=xay \land |y| = n)\}.

Exercici 10 (DFAs – propietats decidibles) Demostreu que els problemes computacionals següents són decidibles proporcionant un algorisme (de cost raonable) que els resol.

1. Donat un DFA A, és L(A)=\emptyset?
2. Donat un DFA A, és L(A) un conjunt infinit?
3. Donats dos DFAs A i B, és L(A)=L(B)?
4. Donats dos DFAs A i B, és L(A)\subseteq L(B)?

Exercici 11 (Els llenguatges finits són regulars)  

1. Demostreu que per a tot mot w, el llenguatge \{w\} és regular.

2. Demostreu que tot llenguatge finit, és a dir, tot llenguatge consistent en un nombre finit de mots, és regular.

3. Un llenguatge L és co-finit si el seu complement \overline L és finit. Demostreu que si un llenguatge és cofinit, llavors és regular.

4. Mostreu que el llenguatge L=\{0^n \mid \text{l’expansió decimal de $\pi$ conté $n$ zeros consecutius}\} és regular.

   Ajut

   No cal conèixer cap propietat de l’expansió decimal de \pi (a banda del fet de ser infinita). Penseu en canvi en una demostració per casos no constructiva.

5. Una part crucial de la definició dels DFAs és que només poden tenir un nombre finit d’estats. Demostreu que la definició esdevindria trivial si els DFAs poguessin tenir un nombre infinit d’estats, en el sentit que tot llenguatge (diguem que sobre l’alfabet \{a,b\}) es podria reconèixer amb un DFA si li permetéssim tenir un nombre infinit d’estats.

Exercici 12 (La pertinença a un regular és decidible en temps polinòmic) Considereu el problema decisional següent: \mathtt{Pertinen\c{c}a_{Reg}}: \text{ donada una entrada $x\in \{0,1\}^*$ i $A$ un DFA, determinar si } x\in L(A).

Demostreu \mathtt{Pertinen\c{c}a_{Reg}} es pot decidir en temps polinòmic en |x| i la mida de A.

Exercici 13 (Les progressions aritmètiques són regulars) Sigui \boldsymbol{a}=(a_1,a_2,\dots) una progressió aritmètica, és a dir, una seqüència en la qual la diferència entre dos termes consecutius és constant. L’objectiu d’aquest exercici és (d’una manera una mica informal) mostrar que, independentment de la base triada per representar la progressió aritmètica, això dona lloc a un llenguatge regular.

Més en concret:

1. Demostreu que el llenguatge \{1^m \mid m\in \boldsymbol{a}\} és regular.

2. Donat n\in \mathbb N, quants estats té el DFA mínim que reconeix el llenguatge \{1^m \mid m\in n\mathbb N\}?

3. Demostreu que el llenguatge \{w\in \{0,1\}^* \mid \mathtt{value}_2(w)\in \boldsymbol{a}\} és regular.

4. Donat n\in \mathbb N, quants estats té el DFA mínim que reconeix \{w\in \{0,1\}^* \mid \mathtt{value}_2(w)\in n\mathbb N\} quan n=2^k per a algun k\in \mathbb N? I quan n és senar? I quan n=m2^k per a algun k\in \mathbb N i m és senar?

5. Demostreu que el llenguatge \{w\in \{0,1,2\}^* \mid \mathtt{value}_3(w)\in \boldsymbol{a}\} és regular.

6. Demostreu que el llenguatge \{w\in \Sigma^* \mid \mathtt{value}_b(w)\in \boldsymbol{a}\} és regular, on b \ge 2 and \Sigma=\{0,1,2,\dots,b-1\} és un alfabet de dígits.

Recordeu que, per qualsevol b \ge 2, \mathtt{value}_b(w) representa el nombre obtingut interpretant el mot w com un nombre escrit en base b. Per exemple, \mathtt{value}_2(00101)=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+0\cdot 2^3+0\cdot 2^4=1+4=5, \mathtt{value}_3(0121)=1\cdot 3^0+2\cdot 3^1+1\cdot 3^2+0\cdot 3^3=1+6+9=16.

Exercici 14 (Almenys k ocurrències de cada símbol és un llenguatge regular) Donat k\in \mathbb N, considereu el llenguatge

L_k=\{w\in \{a,b,c\}^* \mid |w|_a\geq k \land |w|_b\geq k \land |w|_c\geq k\}\ .

1. Demostreu que per qualsevol k, L_k és un llenguatge regular.

2. Quants estats (en funció de k) té el mínim DFA que reconeix L_k?

Exercici 15 (La primera meitat d’un regular és regular) Donat un llenguatge L, definim \mathtt{PrimeraMeitat}(L) com el conjunt de mots que constitueixen la primera meitat de mots de mida parella a L, és a dir, \mathtt{PrimeraMeitat}(L)= \{x \mid \exists y \, (|x|=|y| \, \wedge \, xy \in L)\}. Demostreu que si L és regular, aleshores \mathtt{PrimeraMeitat}(L) és regular.

Exercici 16 (L’IntercalAND de regulars és regular) Donats dos llenguatges L_1, L_2 \subseteq \Sigma^*, definim

\mathtt{intercalAND}(L_1,L_2) = \{x_1y_1 ... x_ny_n \mid (n \geq 1) \, \wedge \, (x_1, \dots , x_n ,y_1, \dots ,y_n \in \Sigma) \, \wedge \, (x_1\cdots x_n \in L_1) \, \wedge \, (y_1 \cdots y_n \in L_2)\}.

Demostreu que si L_1 i L_2 són regulars, aleshores \mathtt{intercalAND}(L_1,L_2) també és regular.

Exercici 17 (Prefixos i sufixos) Donat un llenguatge L, definim

\mathtt{Prefixos}(L)=\{w\mid \exists x\ (wx\in L)\}

i

\mathtt{Sufixos}(L)=\{w\mid \exists x\ (xw\in L)\}.

1. Donat un DFA A, com es pot construir un DFA que reconegui el llenguatge \mathtt{Prefixos}(L(A))?

2. Donat un DFA A, com es pot construir un DFA que reconegui el llenguatge \mathtt{Sufixos}(L(A))?

Exercici 18 (Variacions sobre a^n b^n) A classe hem vist que A=\{a^nb^n \mid n\in \mathbb N\} no és un llenguatge regular.

1. Considereu ara un llenguatge L\subseteq A. Demostreu que L és regular si i només si és finit.

   Ajut

   Abans d’intentar obtenir el resultat general, podria ser millor provar alguns casos especials per obtenir idees sobre com procedir en general.

   • Com demostraríeu que \{a^nb^n \mid n\in 2\mathbb N\} no és regular?
   • Com ho demostraríeu amb \{a^nb^n \mid n\in 3\mathbb N\}?

2. Demostreu que els llenguatges següents no són regualars.

   1. \{a^nb^m \mid n,m\in \mathbb N\land n\leq m\}
   2. \{a^nb^m \mid n,m\in \mathbb N\land n\geq m\}
   3. \{a^nb^m \mid n,m\in \mathbb N\land n\neq m\}
   4. \{a^{2n}b^n \mid n\in 2\mathbb N\}
   Ajut

   Fent servir el lema de bombament directament és possible però una mica complicat. És més senzill aplicar primer propietats de tancament dels llenguatges regulars.

3. Demostreu que els llenguatges següents sobre \{a,b,c\} no són regulars.

   1. \{c^ma^nb^n \mid n,m\in \mathbb N\}
   2. \{a^nc^mb^n \mid n,m\in \mathbb N\}
   3. \{a^nb^nc^m \mid n,m\in \mathbb N\}
   4. \{a,b\}^* \cup \{c^ma^nb^n \mid n,m\in \mathbb N\}

4. Demostreu que el llenguatge de Dyck, és a dir, el llenguatge de tots els parèntesis ben formats, no és regular. En concret, donat l’alfabet \Sigma=\{(,)\}, demostreu que el llenguatge \{w\in \Sigma^* \mid |w|_(=|w|_) \land \text{per a tot prefix $u$ de $w$} \ \ |u|_(\geq |u|_)\}

   no és regular.

Exercici 19 (Comptar as i bs no és regular (en general)) Demostreu que els llenguatges següents no són regulars.

1. \{w\in \{a,b\}^* \mid |w|_a = |w|_b\}
2. \{w\in \{a,b\}^* \mid |w|_a \geq |w|_b\}
3. \{w\in \{a,b\}^* \mid |w|_a \leq |w|_b\}
4. \{w\in \{a,b\}^* \mid |w|_a \neq |w|_b\}
5. \{w\in \{a,b,c\}^* \mid |w|_a \geq |w|_b \lor |w|_b\geq |w|_c \}
6. \{w\in \{a,b\}^* \mid |w|\in 3\mathbb N \Rightarrow |w|_a = |w|_b \}

Exercici 20 (Sobre as en la primera part i bs en la segona) Donat k\in \mathbb N, demostreu que L_k=\{xy\in \{a,b\}^* \mid |x|_a=k|y|_b\} és regular si i només si k=1 o k=0.

Ajut

La part difícil és demostrar que per a k>1, el llenguatge L_k no és regular. Penseu primer en k=2. L’argument per a una k genèrica és una simple generalització d’aquest cas.

Més ajut

Considereu el revessat de L_2.

Exercici 21 (Palíndroms i palíndroms parcials)  

1. Demostreu que el llenguatge \{w\in \{a,b\}^* \mid w=w^R\} no és regular.

2. Demostreu que el llenguatge \{ww^R\mid w\in \{a,b\}^*\} no és regular.

3. Demostreu que el llenguatge \{ww\mid w\in \{a,b\}^*\} no és regular.

4. (difícil) Demostreu que el llenguatge \{ww^Rx\mid w,x\in \{a,b\}^+\} no és regular.

   Precaució

   En aquest últim punt, el lema de bombament no permet demostrar la no regularitat. Per què?

   Ajut

   Suposeu, per arribar a contradicció, que el llenguatge és regular i existeix un DFA de N estats que el reconeix. Comproveu el comportament de l’autòmat amb tots els mots w_i=aba^2b^2\cdots a^ib^i, per a i=1,2,\dots, N+1.

Exercici 22 (Comprovar aritmètica bàsica no és regular) Demostreu que els llenguatges següents sobre l’alfabet \{0,1,\#\} no són regulars.

1. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ v\text{ és submot de }u\}
2. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ (|u|<|v|\lor |u|\in 2\mathbb N)\}
3. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)=\mathtt{value}_2(v)\}
4. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)=\mathtt{value}_2(v)+1\}
5. \{u\#v\#z \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)+\mathtt{value}_2(v)=\mathtt{value}_2(z)\}

Exercici 23 (Aproximacions de nombres reals) Donat un nombre real r\in [0,1), sigui L_r \subseteq \{0,1\}^* el llenguatge consistent en els mots no buits w, on w coincideix amb els primers |w| dígits de l’expansió binària de r. Per exemple,

• 1/2 en binari és .1 i, per tant, L_{1/2}=\{1, 10, 100, 1000, \dots\}
• 1/3 en binari és .01010101\dots i, per tant, L_{1/3}=\{0, 01, 010,0101,01010, \dots\}

1. Demostreu que L_r és un llenguatge regular si i només si r és un nombre racional.
2. Argumenteu per què per a gairebé tots els nombres reals r\in [0,1), L_r no és un llenguatge regular.

Exercici 24 (Seqüències unàries amb forats arbitràriament grans) Sigui \boldsymbol a=(a_1,a_2,a_3,\dots) una seqüència ordenada de nombres naturals. Diem que la seqüència \boldsymbol a té forats arbitràriament grans si per tot n\in \mathbb N hi ha un índex i tal que a_{i+1}>a_i +n.

1. Demostreu que {\boldsymbol a} té forats arbitràriament grans quan

   1. a_i=2^i
   2. a_i=i^2
   3. a_i és l’i-èsim nombre de Fibonacci
   4. a_i is l’i-èsim nombre primer

2. Donada una seqüència \boldsymbol a amb forats arbitràriament grans, demostreu que el llenguatge L_{\boldsymbol a}=\{1^{k} \mid k\in \boldsymbol a\} no és regular.

   Ajut

   Proveu a demostrar que L_{\boldsymbol a} no és regular en els dos casos següents abans de demostrar el resultat general: a_i=2^i i a_i=i^2. Això us podria donar idees sobre com procedir en el cas general.

3. Utilitzant les idees dels apartats anteriors, demostreu que els llenguatges següents no són regulars:

   1. \{0101^201^3\cdots01^n \mid n\in \mathbb N\}
   2. \{1^n \mid n\text{ és parell o primer}\}

Exercici 25 (Quines operacions preserven la no regularitat?) Quins dels llenguatges següents podem assegurar que no són regulars sabent que A i B no són regulars i que \sigma és un homomorfisme?

1. \bar{A}.
2. A\cup B.
3. A\cap B.
4. A\cdot B.
5. A^R.
6. A^*.
7. S(A) (recordeu que S(A) representa el desplaçament o shift d’un llenguatge A, vegeu la Tasca 1).
8. \sigma(A).
9. \sigma^{-1}(A).

Exercici 26 (Lema d’Arden i aplicacions)  

1. Lema d’Arden. Donats els llenguatges A,B\subseteq \Sigma^* i l’equació X=AX\cup B, \tag{1}

   demostreu que

   1. X=A^*B és solució de (Equació 1), és a dir, A^*B=AA^*B\cup B;
   2. si L és solució de (Equació 1), llavors L\supseteq A^*B;
   3. si \lambda\notin A, llavors A^*B és l’única solució de (Equació 1).

2. Versió simètrica del Lema d’Arden. Donats els llenguatges A,B\subseteq \Sigma^* i l’equació Y=YA\cup B, \tag{2}

   demostreu que

   1. Y=BA^* és solució de (Equació 2);
   2. si L és solució de (Equació 2), llavors L\supseteq BA^*;
   3. si \lambda\notin A, llavors BA^* és l’única solució de (Equació 2).

3. Per a cadascun dels llenguatges següents L, doneu un DFA A_L que reconegui L i dues expressions regulars que representin L. Obtingueu les expressions regulars fent servir el lema d’Arden i la versió simètrica del lema d’Arden sobre A_L on

   1. L és el llenguatge dels mots sobre \{a,b\} amb un nombre parell d’as;
   2. L és el llenguatge dels mots sobre \{a,b\} amb o bé un nombre parell d’as o bé un nombre parell de bs;
   3. L és el llenguatge dels mots sobre \{a,b\} que acaben en ababa;
   4. L és el llenguatge dels mots sobre \{a,b\} que no contenen el submot aba;
   5. L és el llenguatge dels mots sobre \{a,b,c\} tals que entre cada dues as hi ha almenys una b;
   6. L és el llenguatge dels mots sobre \{0,1\} amb almenys dos 0s consecutius;
   7. L=\overline{\{w\in \{0,1\}^*\mid \mathtt{value}_2(w)\in 3\mathbb N\}}.
   Consell

   Donat un DFA A, podem associar dues variables a cada estat q: \begin{aligned} X_q&=\text{el llenguatge dels mots que porten de $q$ a un estat acceptador en $A$} \\ Y_q&=\text{el llengutge dels mots que porten de l'estat inicial a $q$ en $A$} \end{aligned} Utilitzant les variables anteriors, podem establir dos sistemes d’equacions i resoldre-les fent ús del lema d’Arden (i de la seva versió simètrica). El sistema que utilitza les variables X_q es pot resoldre amb el lema d’Arden, mentre que el que utilitza Y_q es pot resoldre amb la versió simètrica del lema.

Exercici 27 (Expressions regulars i propietats de tancament dels regulars) Sabem que les expressions regulars representen exactament els llenguatges regulars i que els llenguatges regulars són tancats per diverses operacions. Aquest exercici tracta de trobar expressions regulars per als llenguatges després d’aplicar-los una d’aquestes operacions.

Donades les expressions regulars r_1 i r_2 com a entrada, que representen respectivament els llenguatges L_1 i L_2, per construcció (r_1)+(r_2), (r_1)(r_2), and (r_1)^* representen els llenguatges L_1\cup L_2, L_1L_2 i L_1^* respectivament. Què es pot dir de les altres operacions que preserven la regularitat?

1. (complementari) Donada una expressió regular r com a entrada, que representa el llenguatge L, doneu un algorisme per trobar l’expressió regular que representa el llenguatge \overline{L}. Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r?

2. (intersecció) Donades dues expressions regulars r_1 i r_2 com a entrada, que representen els llenguatges L_1 i L_2 respectivament, doneu un algorisme per trobar una expressió regular que representi el llenguatge L_1\cap L_2. Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r_1 i r_2?

3. (revessat) Donada una expressió regular r com a entrada, que representa el llenguatge L, doneu un algorisme per trobar una expressió regular que representi el llenguatge L^R. Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r?

4. (homomorfisme) Donada una expressió regular r com a entrada, que representa el llenguatge L, i un homomorfisme \sigma, doneu un algorisme per trobar una expressió regular que representi el llenguatge \sigma(L).

5. (homomorfisme invers) Donada una expressió regular r com a entrada, que representa el llenguatge L, i un homomorfisme \sigma, doneu un algorisme per trobar una expressió regular que representi el llenguatge \sigma^{-1}(L).

Exercici 28 (Propietats decidibles sobre expressions regulars) Sigui L_r el llenguatge (regular) representat per l’expressió regular r. Donades dues expressions regulars r i s com a entrada, descriviu un algorisme per decidir si

1. L_{r}=L_{s}.
2. L_{r}\subseteq L_{s}.
3. L_{r}=\emptyset.
4. L_{r} és infinit.
5. L_{r}\cap L_{s}=\emptyset.
6. L_{r}\cap L_{s} és infinit.

Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r i s?

Exercici 29 (Transformació d’expressions regulars) Diem que dues expressions regulars p,q són equivalents (p\equiv q) si els llenguatges associats a p i a q (resp. L(p) i L(q)) són iguals. Per comprovar si dues expressions regulars p,q són equivalents, sempre podríem construir els DFAs associats i comprovar si accepten el mateix llenguatge. Això és car computacionalment.¹

Aquest exercici tracta sobre l’equivalència d’expressions regulars basada en manipulacions algebraiques senzilles. Demostreu que per a qualssevol expressions regulars p, q i r:

1. (p+q)^* \equiv p^*(qp^*)^*.
2. p(qp)^* \equiv (pq)^*p.
3. (p+q^*)^* \equiv (p+q)^*.
4. Si p\equiv q, llavors pr \equiv qr i rp \equiv rq.
5. Si L(q) \subseteq L(p), llavors p^*q^* \equiv q^*p^* \equiv p^*.
6. p^* \equiv (\lambda + p)^* \equiv (\lambda + p)(p^*pp)^*.
7. p^*pp + \lambda \equiv (p^*pp)^* \equiv (pp+ppp)^*.
8. p^*(q+rp^*)^* \equiv (p+q^*r)^*q^*.
9. (qq+qp+p)^*qpp^* \equiv p^*q(pp^*q+qp^*q)^*pp^*.
10. (\lambda + b)a^*(b + bba^*)^* \equiv b^*(a + bb + bbb)^*b^*.

Consell

Per demostrar alguns apartats (especialment, els tres darrers), és útil aplicar equivalències prèvies.

Notes a peu de pàgina

1. Decidir si dues expressions regulars són equivalents és \mathbf{PSPACE}-complet, és a dir, informalment, és entre els problemes decisionals més difícils que requereixen una quantitat polinòmica de memòria, però sense limitacions sobre el temps de càlcul.