Siguiente: Autómatas de pila Un nivel arriba: Expresiones regulares Anterior: Ejercicios

Programas

1. Máquinas de Mealy como ``traductores'': Recordamos que una máquina de Mealy es una estructura de la forma

$$\mbox{\it MMe\/}=(Q,\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/},\mbox{\it res\/},q_0)$$

donde, para fines de este ejercicio:

$$\begin{eqnarray*}Q &=& [\![1,n]\!] \mbox{\rm es el conjunto de {\em estados},} \... ...sta}, y} \\ q_0 &=& 1 \mbox{\rm es el estado {\em inicial}.} \end{eqnarray*}$$

Escriba un programa que reciba como entrada los números enteros n,m,M y los arreglos $\mbox{\it tran\/}$ y $\mbox{\it res\/}$. Posteriormente, para cada cadena $\sigma \in \mbox{\it Ent\/}^*$ dada, ha de calcular la cadena de respuesta $\mbox{\it res\/}^*(\sigma)\in\mbox{\it Sal\/}^*$.

2. Máquinas de Moore como ``traductores'': Recordamos que una máquina de Moore es una estructura de la forma

$$\mbox{\it MMo\/}=(Q,\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/},\mbox{\it res\/},q_0)$$

donde, para fines de este ejercicio:

$$\begin{eqnarray*}Q &=& [\![1,n]\!] \mbox{\rm es el conjunto de {\em estados},} \... ...sta}, y} \\ q_0 &=& 1 \mbox{\rm es el estado {\em inicial}.} \end{eqnarray*}$$

Escriba un programa que reciba como entrada los números enteros n,m,M y los arreglos $\mbox{\it tran\/}$ y $\mbox{\it res\/}$. Posteriormente, para cada cadena $\sigma \in \mbox{\it Ent\/}^*$ dada, ha de calcular la cadena de respuesta $\mbox{\it res\/}^*(\sigma)\in\mbox{\it Sal\/}^*$.

3. Equivalencia entre máquinas de Mealy y de Moore: Escriba un programa que dada una máquina de Mealy, en la representación descrita para el programa 1 de esta lista, calcule la máquina de Moore equivalente, tal que todos sus estados sean accesibles, y la exprese en la representación descrita para el programa 2 de esta lista.

4. Indistinguibilidad en máquinas de Moore:

1.

Dada una máquina de Moore M, dos estados q_i,q_j son indistiguibles si para cualquier palabra $\sigma \in \mbox{\it Ent\/}^*$ las respuestas de los estados a los que se llega con $\sigma$, partiendo de q_i y de q_j, coinciden. Esta es una relación de equivalencia entre estados. Escriba un programa que dada una máquina de Moore M calcule al cociente $M/\mbox{\it Ind\/}$.

2.

Dada una máquina de Moore M, dos palabras $\sigma_1,\sigma_2\in\mbox{\it Ent\/}^*$ son indistiguibles si los estados a los que llegan, partiendo del inicial, $\mbox{\it tran\/}^*(q_0,\sigma_1)$ y $\mbox{\it tran\/}^*(q_0,\sigma_2)$ son indistinguibles. Esta es una relación de equivalencia entre palabras. Escriba un programa que dada una máquina de Moore M calcule al cociente $\mbox{\it Ent\/}^*/\mbox{\it Ind\/}$.

3.

¿Qué relación hay entre los cocientes encontrados para una misma máquina?

Nota: En lo que sigue, un semiautómata de n estados con m símbolos se representará como una matriz S del tipo $[\![1,n]\!]^{m\times n}$, con la intención obvia de que $\forall i,j:\ s_{ij}$ es el índice del estado al que se llega desde el estado j cuando se aplica el símbolo i. Un autómata se representará como una pereja (S,F), donde $F\subset[\![1,n]\!]$ es el conjunto de índices de estados finales.




5. Parte accesible de un autómata finito: Dado un autómata, calcule la parte accesible del autómata, y renombre, si fuera necesario, al conjunto de estados resultante para expresarlo con la convención que aquí hemos adoptado para representar autómatas.

6. Homomorfismos de autómatas: Escriba un programa que dados dos autómatas decida si hay un homomorfismo del primer autómata al segundo. Si $h:\mbox{\it AF\/}_1\to \mbox{\it AF\/}_2$ fuese un homomorfismo entre dos autómatas, diga que dos estados q_i¹,q_j¹ son equivalentes si h(q_i¹)=h(q_j¹). Esta es, en efecto, una relación de equivalencia. Calcule sus clases de equivalencia.

7. Monoides de autómatas deterministas: Escriba un programa que reciba un autómata determinista y calcule la tabla de multiplicación de su monoide. (Cfr. Sec. 4.2.2 de las ``Notas del Curso'').

8. Acciones de grupos libres en monoides: Suponga dado un monoide $M\in [\![1,n]\!]^{n\times n}$, por su tabla de multiplicación, con unidad, digamos u=1. Para un conjunto no-vacío de elementos $I\subset [\![1,n]\!]$ denotamos por [I]_M al mínimo submonoide, del monoide M, que contiene al conjunto I. [I]_M es el submonoide generado por I en M. Si I consta de un único elemento, digamos $I=\{a\}$, $a\not=u$, el submonoide [I]_M se calcula como sigue:

1.

Inicialmente hágase $[I]_M=\{1\}=\{a^0\}$, y $\mbox{\it PorProbar\/}=I$.

2.

Mientras que $\mbox{\it PorProbar\/}\not=\emptyset$, sáquese el primer elemento x, digamos x=aⁱ, que quede en $\mbox{\it PorProbar\/}$ y añádasele a [I]_M. Tómese ahora $y=x\cdot a=a^{i+1}$. Si y no aparece aún en [I]_M colóquese y en la lista $\mbox{\it PorProbar\/}$.

3.

Cuando no queden elementos por probar, el submonoide generado por a queda en [I]_M y a partir de ahí es posible construir la tabla de multiplicación de $[\{a\}]_M$.

Si I consta de más de un elemento, digamos $I=\{a_1\ldots,a_{k-1},a_k\}$, $\forall i\leq k:\ a_i\not=u$, el submonoide [I]_M se calcula como sigue:

1.

Inicialmente hágase $[I]_M=[\{a_1\ldots,a_{k-1}\}]_M$, el submonoide generado por los primeros k-1 elementos, y $\mbox{\it PorProbar\/}=\{a_k\}$.

2.

Mientras que $\mbox{\it PorProbar\/}\not=\emptyset$, sáquese el primer elemento x, que quede en $\mbox{\it PorProbar\/}$. Si acaso ya estuviese en [I]_M termínese el proceso sin más. En otro caso, añádasele a [I]_M y para cada elemento z en [I]_M, tómese $y_{\mbox{\scriptsize\it der}}=z\cdot x$ e $y_{\mbox{\scriptsize\it izq}}=x\cdot z$. Si $y_{\mbox{\scriptsize\it der}}$ no aparece ni en [I]_M ni en $\mbox{\it PorProbar\/}$, colóquese $y_{\mbox{\scriptsize\it der}}$ en la lista $\mbox{\it PorProbar\/}$. Si $y_{\mbox{\scriptsize\it izq}}$ no aparece ni en [I]_M ni en $\mbox{\it PorProbar\/}$, colóquese $y_{\mbox{\scriptsize\it izq}}$ en la lista $\mbox{\it PorProbar\/}$.

3.

Cuando no queden elementos por probar, el submonoide generado por I queda en [I]_M y a partir de ahí es posible construir la tabla de multiplicación de [I]_M.

Escriba un programa que dado un monoide en M encuentre un conjunto mínimo de elementos $I=\{a_1\ldots,a_{k-1},a_k\}$ tal que M=[I]_M.

9. Autómatas de máximos monoides: (Este programa se ha de apoyar de manera esencial en el programa anterior en esta lista.) Dado n considere un conjunto Q de n estados, para fijar ideas, $Q=[\![1,n]\!]$. Sea ${\cal F}_n=\left(f_{i}^{(n)}\right)_{i=1}^{n^n}$ una enumeración de todas las funciones $Q\to Q$. ${\cal F}_n$ es un monoide con la composición de funciones como operación. Sea m=nⁿ y sea A_n un subconjunto de m símbolos. Consideremos el semiautómata ${\cal A}_n = (Q,A_n,\mbox{\it tran\/},1)$ tal que $\mbox{\it tran\/}:(q,a_{in})\mapsto f_{in}(q)$. Entonces su monoide, naturalmente coincide con ${\cal F}_n$ y posee nⁿ elementos. Escriba un programa que reduzca el semiautómata ${\cal A}_n$ a uno ${\cal A}'_n$ sobre un alfabeto mínimo $A'_n\subset A_n$ tal que el monoide del semiautómata reducido ${\cal A}'_n$ coincida también con ${\cal F}_n$.

10. Indistinguibilidad de estados en autómatas: Para un autómata $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ se tiene la relación en Q:

$$\forall p,q\in Q:\ \ p\equiv_{\mbox{\scriptsize\it Ind}} q\ \... ... F\ \ \Leftrightarrow\ \ \mbox{\it tran\/}^*(q,\sigma)\in F]$$ (50)

Escriba un programa que dado un autómata calcule el autómata cociente correspondiente a esta relación. Extienda este programa para que dado un autómata calcule el mínimo autómata equivalente.

11. Monoides de autómatas no-deterministas: Escriba un programa que reciba un autómata no-determinista y calcule la tabla de multiplicación de su monoide. (Cfr. Sec. 4.3.2 de las ``Notas del Curso'').

12. No-Determinismo = Determinismo: Escriba un programa que reciba un autómata no-determinista o una gráfica de transición y calcule el autómata determinista equivalente al dispositivo dado. (Cfr. Sec. 4.3 y 4.4 de las ``Notas del Curso'').

13. Bidireccionalidad = Monodireccionalidad: Escriba un programa que reciba un autómata bidireccional y calcule el autómata (monodireccional) equivalente al dispositivo dado. (Cfr. Sec. 4.5 de las ``Notas del Curso'').

14. Analizador de expresiones regulares: Escriba un programa que reciba una expresión regular $X\in\mbox{\it ER\/}$, calcule una gráfica de transición cuyo lenguaje sea el expresado por X. (Cfr. Sec. 5.2 de las ``Notas del Curso'').

15. Seudoinversión matricial con expresiones regulares: Escriba un programa que reciba una matriz $\mbox{\bf A}\in\mbox{\it ER\/}^{n\times n}$, con $n\leq 5$, y calcule $\mbox{\bf A}^*$. (Cfr. Sec. 5.4 de las ``Notas del Curso'').

16. Caracterización de lenguajes regulares: Utilizando el programa del ejercicio anterior, escriba un programa que reciba un autómata determinista y calcule una expresión regular que represente al lenguaje del autómata. (Cfr. Sec. 5.2 de las ``Notas del Curso'').

17. Reconocedores de lenguajes finitos: Escriba un programa que reciba un conjunto finito de palabras y construya el autómata finito que reconoce únicamente a las palabras dadas.

18. Contención de lenguajes regulares: Escriba un programa que dadas dos expresiones regulares determine si la primera está contenida, y en caso que no, encuentre una palabra en el primer lenguaje que no esté en el segundo.

19. Reconocedor de subpalabras: Escriba un programa que dado un conjunto de k palabras, $\{\sigma_1,\ldots,\sigma_n\}$, construya una máquina de Moore, con alfabeto de salida $\left(a_K\right)_{K\subset[\![1,n]\!]}$, tal que para cualquier palabra dada $\tau$ la respuesta del autómata tras de leer $\tau$ será a_K, donde $K=\{i\vert\sigma_i\mbox{\rm es una subpalabra de }\tau\}$.

20. Reconocedor de caminos: Sea G=(V,D), con $D\subset V\times V$, una gráfica dirigida. Una camino es una sucesión de aristas $\left(a_i=(v_{i1},v_{i2})\right)_i$ tal que $\forall i:\ v_{i2}=v_{i+1,1}$. Escriba un programa que dada una gráfica dirigida, construya un autómata sobre el alfabeto de aristas en la gráfica que reconozca exactamente a los caminos en la gráfica.

21. Reverso de elenguajes regulares: Escriba un programa que dado un autómata finito $\mbox{\rm AF}$ construya el autómata finito $\mbox{\rm AF}^R$ tal que $L(\mbox{\rm AF}^R)=L(\mbox{\rm AF})^R=$ (reverso del lenguaje reconocido por AF).

22. Cadenas minimales en lenguajes regulares: Para un lenguaje L sea

$$\mathop{\rm Min}(L)=\{\sigma \in L\vert\forall \tau\in L-\{\m... ...\mbox{\scriptsize\it prefijo}}\tau \ \Rightarrow\ \sigma=\tau\}$$

el lenguaje consistente de las palabras en L que no poseen prefijo propio en L. Escriba un programa que dado un autómata finito $\mbox{\rm AF}$ construya el autómata finito $\mathop{\rm Min}(\mbox{\rm AF})$ tal que $L(\mathop{\rm Min}(\mbox{\rm AF}))=\mathop{\rm Min}L(\mbox{\rm AF})$.

23. Cadenas maximales en lenguajes regulares: Para un lenguaje L sea

$$\mathop{\rm Max}(L)=\{\sigma \in L\vert\forall \tau\in L:\sig... ...\mbox{\scriptsize\it prefijo}}\tau \ \Rightarrow\ \sigma=\tau\}$$

el lenguaje consistente de las palabras en L que no son prefijo propio de ninguna otra palabra en L. Escriba un programa que dado un autómata finito $\mbox{\rm AF}$ construya el autómata finito $\mathop{\rm Max}(\mbox{\rm AF})$ tal que $L(\mathop{\rm Max}(\mbox{\rm AF}))=\mathop{\rm Max}L(\mbox{\rm AF})$.

24. Regularidad de estrellas en alfabetos mónicos: Escriba un programa que dado un conjunto finito de índices $I\subset I\!\!N$, construya un autómata, sobre el alfabeto $A=\{a\}$ de un único símbolo, que reconozca al lenguaje ${\displaystyle L=\left(\sum_{i\in I} a^i\right)^*}$.

25. Palíndromas de lenguajes regulares: Para un lenguaje L sea

$$L^{\mbox{\scriptsize\it especular}}=\{\sigma \vert\exists \tau\in L:\ \sigma=\tau\tau^R\}$$

el lenguaje consistente de palíndormas con una ``primera parte'' en L, es decir de palabras, e imágenes especulares, en L. Escriba un programa que dada una expresión regular E construya el autómata finito $\mbox{\rm AF}^{\mbox{\scriptsize\it especular}}$ tal que $L(\mbox{\rm AF}^{\mbox{\scriptsize\it especular}})=L(E)^{\mbox{\scriptsize\it especular}}$, donde L(E) es el lenguaje expresado por E. Sugerencia: Razonando por inducción en la construcción de la expresión E, tranfórmela en una expresión que exprese al lenguaje $L(E)^{\mbox{\scriptsize\it especular}}$ y a partir de ella construya al autómata pedido.

26. Raíces n-ésimas de lenguajes regulares: Para un lenguaje L y un entero n, sea

$$\sqrt[n]{L}=\{\sigma \vert\exists \tau\in L:\ \sigma=\tau^n\}$$

el lenguaje consistente de n repeticiones de una ``primera parte'' en L. Escriba un programa que dada una expresión regular E construya el autómata finito $\sqrt[n]{\mbox{\rm AF}}$ tal que $L(\sqrt[n]{\mbox{\rm AF}})=\sqrt[n]{L(E)}$, donde L(E) es el lenguaje expresado por E. Sugerencia: Razonando por inducción en la construcción de la expresión E, transfórmela en una expresión que exprese al lenguaje $\sqrt[n]{L(E)}$ y a partir de ella construya al autómata pedido.

27. Rotaciones de lenguajes regulares: Para un lenguaje L sea

$$\mbox{\it rota\/}(L)=\{\sigma \vert\exists \tau,\upsilon:\ \sigma=\tau\upsilon\ \&\ \upsilon\tau\in L\}$$

el lenguaje consistente de transposiciones de dos partes en L. Escriba un programa que dada una expresión regular E construya el autómata finito $\mbox{\it rota\/}(\mbox{\rm AF})$ tal que $L(\mbox{\it rota\/}(\mbox{\rm AF}))=\mbox{\it rota\/}(L(E))$, donde L(E) es el lenguaje expresado por E.

28. Autómatas no-deterministas-$\Pi$: Un autómata no-determinista-$\Pi$ (AND-$\Pi$) es un autómata no-determinista con la noción de reconocimiento cambiada: Una palabra es reconocida si toda computación, a partir de ella, en el autómata la conduce a un estado final. Escriba un programa que transforme a un AND-$\Pi$ en un autómata finito equivalente.
Siguiente: Autómatas de pila Un nivel arriba: Expresiones regulares Anterior: Ejercicios