Tema 2.   Autòmats Finits

Obtén los DFA’s mínimos $A_{1},A_{2}$ para $L_{1}=\{xaay\mid x,y\in\{a,b\}^{*}\}$ y $L_{2}=\{xbby\mid x,y\in\{a,b\}^{*}\}$, respectivamente, y calcula explícitamente el DFA intersección $A_{1}\cap A_{2}$, determinízalo y minimízalo.

Obtén los DFA’s mínimos $A_{1},A_{2}$ para $L_{1}=\{xaay\mid x,y\in\{a,b\}^{*}\}$ y $L_{2}=\{xbby\mid x,y\in\{a,b\}^{*}\}$, respectivamente, y calcula explícitamente el DFA unión $A_{1}\cup A_{2}$, determinízalo y minimízalo.

Obtén los DFA’s mínimos $A_{1},A_{2}$ para $L_{1}=\{xay\mid x,y\in\{a,b\}^{*}\}$ y $L_{2}=\{xbbby\mid x,y\in\{a,b\}^{*}\}$, respectivamente, y calcula explícitamente el DFA unión $A_{1}\cup A_{2}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{aaw\mid w\in\{a,b\}^{*}\}$, y calcula explícitamente $\overline{A}$.

Obtén el DFA mínimo $A$ para $L=\{w\in\{0,1\}^{*}\mid\mathtt{valor}_{2}(w)\in\dot{3}\}$, y calcula explícitamente $\overline{A}$.

Obtén el DFA mínimo $A$ para $L=\{w\in\{0,1\}^{*}\mid|w|\in\dot{3}+1\}$, y calcula explícitamente $\overline{A}$.

Obtén los DFA’s mínimos $A_{1},A_{2}$ para $L_{1}=\{xaya\mid x,y\in\{a,b\}^{*}\}$ y $L_{2}=\{bxby\mid x,y\in\{a,b\}^{*}\}$, respectivamente, y calcula explícitamente el $\lambda$-NFA concatenación $A_{1}\cdot A_{2}$, determinízalo y minimízalo.

Obtén los DFA’s mínimos $A_{1},A_{2}$ para $L_{1}=\{xaay\mid x,y\in\{a,b\}^{*}\}$ y $L_{2}=\{bxb\mid x\in\{a,b\}^{*}\}$, respectivamente, y calcula explícitamente el NFA concatenación $A_{1}\cdot A_{2}$, determinízalo y minimízalo.

Obtén los DFA’s mínimos $A_{1},A_{2}$ para $L_{1}=\{xaya\mid x,y\in\{a,b\}^{*}\}$ y $L_{2}=\{bxb\mid x\in\{a,b\}^{*}\}$, respectivamente, y calcula explícitamente el NFA concatenación $A_{1}\cdot A_{2}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{xay\in\{a,b\}^{*}\mid|y|=1\}$, y calcula explícitamente el NFA estrella $A^{*}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{xaby\in\{a,b\}^{*}\mid|y|=1\}$, y calcula explícitamente el NFA estrella $A^{*}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{axaby\in\{a,b\}^{*}\mid|y|=1\}$, y calcula explícitamente el NFA estrella $A^{*}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{w\in\{a,b\}^{*}\mid\forall w_{1},w_{2}(w=w_{1}aw_{2}\Rightarrow|w_{1}|_{b}\in\dot{2})\}$, y calcula explícitamente el NFA reverso $A^{R}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{w\in\{a,b\}^{*}\mid\forall w_{1},w_{2}(w=w_{1}aw_{2}\Rightarrow|w_{1}|_{b}\in\dot{2}+1)\}$, y calcula explícitamente el NFA reverso $A^{R}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{w\in\{a,b\}^{*}\mid\forall w_{1},w_{2}(w=w_{1}aw_{2}\Rightarrow|w_{1}|\in\dot{2})\}$, y calcula explícitamente el NFA reverso $A^{R}$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{axbya\mid x,y\in\{a,b\}^{*}\}$, y dado el morfismo definido por $\sigma(a)=aa,\;\sigma(b)=ba$, calcula explícitamente el NFA imagen $\sigma(A)$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{axbyc\mid x,y\in\{a,b,c\}^{*}\}$, y dado el morfismo definido por $\sigma(a)=ab,\;\sigma(b)=b,\;\sigma(c)=\lambda$, calcula explícitamente el NFA imagen $\sigma(A)$, determinízalo y minimízalo.

Obtén el DFA mínimo $A$ para $L=\{xbcya\mid x,y\in\{a,b,c\}^{*}\}$, y dado el morfismo definido por $\sigma(a)=bbb,\;\sigma(b)=a,\;\sigma(c)=\lambda$, calcula explícitamente el NFA imagen $\sigma(A)$, determinízalo y minimízalo.

Sea $A$ el DFA mínimo que reconoce a los números binarios múltiples de $3$. Calcula $\sigma^{-1}(A)$ tomando como $\sigma$ los morfismos:

1. ($a$)  
   ​

   $\sigma(a)=01,\;\sigma(b)=0,\;\sigma(c)=\lambda$.

2. ($b$)  
   ​

   $\sigma(a)=10,\;\sigma(b)=0,\;\sigma(c)=\lambda$.

3. ($c$)  
   ​

   $\sigma(a)=00,\;\sigma(b)=11,\;\sigma(c)=\lambda$.

4. ($d$)  
   ​

   $\sigma(a)=001,\;\sigma(b)=101,\;\sigma(c)=0$.

Diseña un algoritmo de coste razonable para encontrar los estados no accesibles de un DFA de entrada.

Diseña un algoritmo de coste razonable para decidir si un DFA de entrada acepta alguna palabra.

Diseña un algoritmo de coste razonable para decidir si un DFA de entrada acepta infinitas palabras.

Cuál es el coste del algoritmo de determinización de NFA’s en DFA’s.

Cuál es el coste temporal de las siguentes operaciones de DFA’s:

1. ($a$)  
   ​

   intersección.

2. ($b$)  
   ​

   unión.

3. ($c$)  
   ​

   complementario.

4. ($d$)  
   ​

   concatenación (incluyendo determinización).

5. ($e$)  
   ​

   estrella (incluyendo determinización).

6. ($f$)  
   ​

   reverso (incluyendo determinización).

7. ($g$)  
   ​

   aplicación de morfismo (incluyendo determinización).

8. ($h$)  
   ​

   aplicación de morfismo inverso.

Cuál es el coste del algoritmo de minimización con una implementación razonable.

Propón un algoritmo de coste razonable para saber si dos DFA’s de entrada reconocen el mismo lenguaje.

Propón un algoritmo de coste razonable para saber, si dados dos DFA’s de entrada, el lenguaje generado por el primero está incluido en el lenguaje generado por el segundo.

1. ($a$)  
   ​

   $A_{1}\cap A_{2}$ és DFA mínim.

2. ($b$)  
   ​

   $A_{1}\cup A_{2}$ és DFA mínim.

3. ($c$)  
   ​

   $\bar{A}$ és DFA mínim.

4. ($d$)  
   ​

   $\sigma(A)$ és DFA.

5. ($e$)  
   ​

   $\sigma^{-1}(A)$ és DFA mínim.

6. ($f$)  
   ​

   $\bar{\bar{A}}=A$.

7. ($g$)  
   ​

   $(B^{R})^{R}=B$.

8. ($h$)  
   ​

   $(B^{*})^{*}=B^{*}$.

9. ($i$)  
   ​

   $(B_{1}B_{2})B_{3}=B_{1}(B_{2}B_{3})$.

10. ($j$)  
    ​

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

11. ($k$)  
    ​

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

12. ($l$)  
    ​

    En el cas en que $A^{R}$ també sigui DFA, llavors podem concloure que és mínim.

Decimos que un NFA es de aceptación única si para cada palabra aceptada existe una única ejecución aceptadora. Demuestra que, para un NFA de aceptación única $A$, $A^{R}$ es un NFA de aceptación única.

Dado un lenguaje $L$, definimos ${\tt Prefijos}(L)$ como el lenguaje $\{w|\exists x:\,(wx\in L)\}$. Dado un DFA $A$, cómo se puede construir un DFA ${\tt Prefijos}(A)$ que cumpla ${\mathcal{L}}({\tt Prefijos}(A))={\tt Prefijos}({\mathcal{L}}(A))$.

Dado un lenguaje $L$, definimos ${\tt Sufijos}(L)$ como el lenguaje $\{w|\exists x:(xw\in L)\}$. Dado un DFA $A$, cómo se puede construir un DFA ${\tt Sufijos}(A)$ que cumpla ${\mathcal{L}}({\tt Sufijos}(A))={\tt Sufijos}({\mathcal{L}}(A))$.

Demostreu que si $L_{1}$ i $L_{2}$ són regulars, aleshores ${\tt intercalAND}(L_{1},L_{2})$ també és regular.

Donat un llenguatge $L$, definim ${\tt FirstHalf}(L)=\{x\,|\exists y:\,(|x|=|y|\,\wedge\,xy\in L)\}$. Demostreu que si $L$ és regular, aleshores ${\tt FirstHalf}(L)$ és regular.

Dado un natural $n$ definimos $L_{n}=\{w\in\{0,1\}^{*}|\exists k:\,({\tt valor}_{2}(w)=k\cdot 2^{n})\}$. Justifica que cualquier $L_{n}$ es regular. Cuantos estados tiene el DFA mínimo que reconoce $L_{n}$?

Sigui $B_{n}=\{a^{k}\,|\,k\,\text{és un múltiple de }n\}$. Demostreu que per a cada $n\geq 1$, el llenguatge $B_{n}$ és regular.

Sigui $C_{n}=\{x\in\{0,1\}^{*}\,|{\tt valor}_{2}(x)\,\text{és un múltiple de }n\}$. Demostreu que per a cada $n\geq 1$, el llenguatge $C_{n}$ és regular.

Demostreu que el llenguatge $L_{n}=\{xay\mid x,y\in\{a,b\}^{*}\;\wedge\;|y|=n\}$, per a $n\geq 0$, té un DFA de $2^{n+1}$ estats.

Cuantos estados tiene el DFA mínimo que reconoce las palabras sobre $\{a,b,c\}$ que contienen al menos $100$ ocurrencias de cada uno de estos tres símbolos?