Ejercicios para la evaluación continua
Tema 2: Autòmats Finits
Quan diem calcula explícitamente, volem dir calculeu l’autòmat aplicant l’algorisme pertinent (intersecció d’autòmats, reunió d’autòmats, …) explicant la costrucció de l’autòmat (intersecció, reunió, ….) i si cal l’algorisme de determinització i l’algorisme de minimització.
Ejercicio 1 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, i calcula explícitamente el DFA intersección A_1\cap A_2, determinízalo i minimízalo.
Ejercicio 2 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, i calcula explícitamente el DFA unión A_1\cup A_2, determinízalo i minimízalo.
Ejercicio 3 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, i calcula explícitamente el DFA unión A_1\cup A_2, determinízalo i minimízalo.
Ejercicio 4 Obtén el DFA mínimo A para L=\{aaw\mid w\in\{a,b\}^*\}, y calcula explícitamente \overline{A}.
Ejercicio 5 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}.
Ejercicio 6 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}.
Ejercicio 7 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, i calcula explícitamente el \lambda-NFA concatenación A_1\cdot A_2, determinízalo i minimízalo.
Ejercicio 8 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, i calcula explícitamente el NFA concatenación A_1\cdot A_2, determinízalo i minimízalo.
Ejercicio 9 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, i calcula explícitamente el NFA concatenación A_1\cdot A_2, determinízalo i minimízalo.
Ejercicio 10 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 i minimízalo.
Ejercicio 11 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 i minimízalo.
Ejercicio 12 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 i minimízalo.
Ejercicio 13 Obtén el DFA mínimo A para L=\{w\in\{a,b\}^*\mid \forall w_1,w_2(w=w_1aw_2\Rightarrow |w_1|_b\in\dot{2})\}, y calcula explícitamente el NFA reverso A^R, determinízalo i minimízalo.
Ejercicio 14 Obtén el DFA mínimo A para L=\{w\in\{a,b\}^*\mid \forall w_1,w_2(w=w_1aw_2\Rightarrow |w_1|_b\in\dot{2}+1)\}, y calcula explícitamente el NFA reverso A^R, determinízalo i minimízalo.
Ejercicio 15 Obtén el DFA mínimo A para L=\{w\in\{a,b\}^*\mid \forall w_1,w_2(w=w_1aw_2\Rightarrow |w_1|\in\dot{2})\}, y calcula explícitamente el NFA reverso A^R, determinízalo i minimízalo.
Ejercicio 16 Obtén el DFA mínimo A para L=\{axbya\mid x,y\in\{a,b\}^*\}, i dado el morfismo definido por \sigma(a)=aa,\;\sigma(b)=ba, calcula explícitamente el NFA imagen \sigma(A), determinízalo i minimízalo.
Ejercicio 17 Obtén el DFA mínimo A para L=\{axbyc\mid x,y\in\{a,b,c\}^*\}, i dado el morfismo definido por \sigma(a)=ab,\;\sigma(b)=b, \;\sigma(c)=\lambda, calcula explícitamente el NFA imagen \sigma(A), determinízalo i minimízalo.
Ejercicio 18 Obtén el DFA mínimo A para L=\{xbcya\mid x,y\in\{a,b,c\}^*\}, i dado el morfismo definido por \sigma(a)=bbb,\;\sigma(b)=a, \;\sigma(c)=\lambda, calcula explícitamente el NFA imagen \sigma(A), determinízalo i minimízalo.
Ejercicio 19 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:
- \sigma(a)=01,\;\sigma(b)=0,\;\sigma(c)=\lambda.
- \sigma(a)=10,\;\sigma(b)=0,\;\sigma(c)=\lambda.
- \sigma(a)=00,\;\sigma(b)=11,\;\sigma(c)=\lambda.
- \sigma(a)=001,\;\sigma(b)=101,\;\sigma(c)=0.
Ejercicio 20 Diseña un algoritmo de coste razonable para encontrar los estados no accesibles de un DFA de entrada.
Ejercicio 21 Diseña un algoritmo de coste razonable para decidir si un DFA de entrada acepta alguna palabra.
Ejercicio 22 Diseña un algoritmo de coste razonable para decidir si un DFA de entrada acepta infinitas palabras.
Ejercicio 23 Cuál es el coste del algoritmo de determinización de NFA’s en DFA’s.
Ejercicio 24 Cuál es el coste temporal de las siguentes operaciones de DFA’s:
- intersección.
- unión.
- complementario.
- concatenación (incluyendo determinización).
- estrella (incluyendo determinización).
- reverso (incluyendo determinización).
- aplicación de morfismo (incluyendo determinización).
- aplicación de morfismo inverso.
Ejercicio 25 Cuál es el coste del algoritmo de minimización con una implementación razonable.
Ejercicio 26 Propón un algoritmo de coste razonable para saber si dos DFA’s de entrada reconocen el mismo lenguaje.
Ejercicio 27 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.
Ejercicio 28 Justifiqueu la veracitat o falsetat de les següents afirmacions per a DFAs mínims A,A_1,A_2, NFAs B,B_1,B_2,B_3 i morfisme \sigma. En cas que les operacions que apareixen hagin estat definides només per a DFAs, assumiu la seva extensió natural a NFAs.
- A_1\cap A_2 és DFA mínim.
- A_1\cup A_2 és DFA mínim.
- \overline{A} és DFA mínim.
- \sigma(A) és DFA.
- \sigma^{-1}(A) és DFA mínim.
- \overline{\overline{A}}=A.
- (B^R)^R=B.
- (B^*)^*=B^*.
- (B_1B_2)B_3=B_1(B_2B_3).
- (B_1B_2)^R=B_2^RB_1^R.
- (B^R)^*=(B^*)^R.
- En el cas en que A^R també sigui DFA, llavors podem concloure que és mínim.
Ejercicio 29 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.
Ejercicio 30 Dado un lenguaje L, definimos \mathtt{Prefijos}(L) como el lenguaje \{w|\exists x:\, (wx\in L)\}. Dado un DFA A, cómo se puede construir un DFA \mathtt{Prefijos}(A) que cumpla {\mathcal L}(\mathtt{Prefijos}(A))=\mathtt{Prefijos}({\mathcal L}(A)).
Ejercicio 31 Dado un lenguaje L, definimos \mathtt{Sufijos}(L) como el lenguaje \{w|\exists x:(xw\in L)\}. Dado un DFA A, cómo se puede construir un DFA \mathtt{Sufijos}(A) que cumpla {\mathcal L}(\mathtt{Sufijos}(A))=\mathtt{Sufijos}({\mathcal L}(A)).
Ejercicio 32 Donats dos llenguatges L_1, L_2 \subseteq \Sigma^* , definim
\mathtt{intercalAND}(L_1,L_2) = \{x_1y_1 ... x_ny_n | (n \geq (a) \, \wedge \, (x_1, ... , x_n ,y_1, ... ,y_n \in \Sigma) \, \wedge \, (x_1... x_n \in L_(a) \, \wedge \, (y_1 ... 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.
Ejercicio 33 Donat un llenguatge L, definim \mathtt{FirstHalf}(L)= \{x \,| \exists y: \, (|x|=|y| \, \wedge \, xy \in L)\}. Demostreu que si L és regular, aleshores \mathtt{FirstHalf}(L) és regular.
Ejercicio 34 Dado un natural n definimos L_n=\{w\in\{0,1\}^*|\exists k: \,(\mathtt{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?
Ejercicio 35 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.
Ejercicio 36 Sigui C_n= \{x \in \{0,1\}^* \, | \mathtt{valor}_2(x) \, \text{és un múltiple de } n\}. Demostreu que per a cada n\geq 1, el llenguatge C_n és regular.
Ejercicio 37 Demostreu que el llenguatge L_n = \{ xay \mid x, i \in \{a,b\}^* \;\wedge\; |y| = n \}, per a n \ge 0, té un DFA minim de 2^{n+1} estats.
Ejercicio 38 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?