next up previous contents
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

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

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

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

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 qi,qj 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 qi y de qj, 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 qi1,qj1 son equivalentes si h(qi1)=h(qj1). 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=ai, 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=nn y sea An 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 nn 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:

 \begin{displaymath}\forall p,q\in Q:\ \ p\equiv_{\mbox{\scriptsize\it Ind}} q\ \...
... F\ \ \Leftrightarrow\ \ \mbox{\it tran\/}^*(q,\sigma)\in F]
\end{displaymath} (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á aK, 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

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

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

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

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

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

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

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

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

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

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.
next up previous contents
Siguiente: Autómatas de pila Un nivel arriba: Expresiones regulares Anterior: Ejercicios
Guillermo Morales-Luna
2000-06-27