Cuadernillo de Ejercicios Sobre Automatas

Cuadernillo de Ejercicios sobre Autómatas Página 1 de 4

Cátedra de Compiladores – Mario Zuluaga Tobón – Universidad Católica de Oriente

CUADERNILLO DE EJERCICIOS SOBRE AUTÓMATAS Nota Aclaratoria Lo más importante de los ejercicios que se proponen a continuación no es la solución en sí misma, sino el proceso mental que se debe seguir para llegar a dicha solución. Solamente busque ayuda, si ha intentado infructuosamente durante un tiempo razonablemente largo y no consigue ver algún camino viable para encontrar la solución. Tenga presente que si no intenta hallar por sí solo la solución, no logrará descubrir los conceptos e ideas que cada ejercicio pretende ilustrar. CÓMO DISEÑAR UN AUTÓMATA? El diseño es un proceso creativo y como tal no tiene una fórmula o una receta. Sin embargo puede ser útil el que usted se coloque en el lugar de la máquina que está intentando diseñar y mire cómo haría para llevar a cabo la tarea que le fue encomendada. Usted ve los símbolos de la cadena de entrada de uno en uno. Después de cada símbolo tiene que decidir si la cadena vista hasta el momento está en el lenguaje. La razón es que usted, como la máquina, no saben cuando es el fin de la cadena, y por eso siempre debe haber una respuesta disponible. Primero, para hacer estas decisiones, tiene que determinar lo que necesita recordar acerca de la cadena a medida que la va leyendo. ¿Por qué no recordar todo lo que ha visto? Porque solo tiene un número finito de estados, lo cual significa una memoria finita. Solo necesita recordar cierta información crucial. Cuál información es la crucial depende del lenguaje particular siendo considerado. Supongamos que ∑ = {0,1} y A = { w | w con un número impar de unos}. Pretendiendo que usted sea el autómata entonces usted recibe una cadena de ceros y unos, símbolo a símbolo. ¿Necesita recordar toda la cadena vista, para determinar si el número de unos es impar? ¡Claro que no! Simplemente recuerde si el número de unos vistos hasta ese momento es par o impar y mantenga registro de esa información a medida que lee símbolos nuevos. Si lee un 1 cambie o conmute la respuesta, pero si lee un 0, deje la respuesta tal cual. ¿Cómo ayuda esto al diseño? Una vez haya determinado la información necesaria a recordar de la cadena a medida que es leída, usted representa esta información como una lista finita de posibilidades. En nuestro caso serán

1. Par hasta el momento, y 2. Impar hasta el momento.

Luego asigne un estado a cada una de las posibilidades. Estos son los estados del autómata: Luego, asigne las transiciones viendo cómo pasar de una posibilidad a otra solamente leyendo un símbolo de la entrada. Si el estado qpar representa la posibilidad par y el estado qimpar la posibilidad

QQ ppaarr QQ iimmppaarr



impar, debería establecer las transiciones para cambiar de estado cuando vea en la entrada un 1 y debe quedarse allí, en el estado qpar, cuando vea en la entrada un 0, como se muestra a continuación: Haciendo un análisis similar se establecen las transiciones para el estado qimpar, como se muestra a continuación: Luego, establezca el estado inicial para que sea el estado correspondiente con haber visto cero símbolos de la entrada hasta ese instante (la cadena vacía ε). En este caso el estado inicial corresponde a qpar porque cero es un número par. Finalmente, establezca los estados de aceptación que correspondan a aquellas posibilidades donde usted quiere aceptar la cadena de entrada. En nuestro caso es qimpar porque queremos aceptar cuando hayamos visto un número impar de unos. EJERCICIOS FUNDAMENTALES Estos ejercicios exigen el tener claro algún concepto o manera de hacer las cosas que posteriormente servirá para enfrentarse a los ejercicios complementarios. No intente realizar los ejercicios más complejos sin primero tener claro el mecanismo de solución para cada ejercicio fundamental (exceptuando los indicados como difíciles). Construya los AFD que acepten los siguientes lenguajes con el alfabeto {0,1}: F1. El conjunto de todas las cadenas terminadas en 00. F2. El conjunto de todas las cadenas con tres ceros consecutivos (no necesariamente al final). F3. El conjunto de las cadenas con 011 como subcadena. F4. El conjunto de las cadenas que comienzan con 0 y tienen longitud impar, o comienzan con 1 y tienen longitud par. F5. El conjunto de las cadenas en donde cada posición impar de la cadena es un 1.

0

QQ iimmppaarr QQ ppaarr

1

QQ iimmppaarr


1

QQ iimmppaarr

0

1

0


1

QQ iimmppaarr

0

1

0



F6. El conjunto de las cadenas que no contengan la subcadena 110. F7. (¡Difícil!) El conjunto de todas las cadenas en las que cada bloque de cinco símbolos consecutivos contiene al menos dos ceros. F8. (¡Difícil) El conjunto de las cadenas en las que el número de ceros sea divisible por cinco y el número de unos sea divisible por tres. F9. Convertir en un AFD cada uno de los AFN de los ejercicios F10, F11 y F12. Diseñar AFN para reconocer los siguientes conjuntos de cadenas: F10. abc, abd y aacd. Asumir que el alfabeto es {a,b,c,d} F11. 0101, 101 y 011. F12. ab, bc y ca. Asumir que el alfabeto es {a,b,c} Diseñar AFN-ε para reconocer los siguientes lenguajes. Intente utilizar transiciones ε para simplificar el diseño. F13. El conjunto de cadenas con cero o más letras a seguidas de cero o más letras b, seguidas de cero o más letras c. F14. (¡Difícil!) El conjunto de cadenas formadas por 01 repetido una o más veces, o por 010 repetido una o más veces. F15. (¡Difícil!) El conjunto de cadenas de ceros y unos que contienen un 1 al menos en una de las diez últimas posiciones. EJERCICIOS COMPLEMENTARIOS Los siguientes ejercicios pretenden darle práctica adicional en todos los conceptos aprendidos en los ejercicios fundamentales, por lo cual no debería intentarlos hacer antes de haber resuelto los primeros. Tenga presente que muchos de los ejercicios complementarios requieren de la mezcla de varios de los conceptos fundamentales para poderlos resolver exitosamente. Construya los AFD que acepten los siguientes lenguajes con el alfabeto {a,b}: C1. { w | w tienen al menos tres aes y al menos dos bes}. C2. { w | w tienen exactamente dos aes y al menos dos bes}. C3. { w | w tienen un número par de aes y una o dos bes}. C4. { w | w tienen un número par de aes y cada a es seguida por al menos una b}. C5. { w | w comienza con una a y tiene como máximo una b}. C6. { w | w tienen un número impar de aes y termina con ab}.



C7. { w | w tienen longitud par y un número impar de aes} C8. { w | w no contenga la subcadena ab} C9. { w | w no contenga ni la subcadena ab ni la subcadena ba} C10. { w | w contiene un número igual de ocurrencias de las subcadenas ab y ba}. Por ejemplo, bab es válida porque contiene una sola ab y una sola ba, pero baba no es válida porque contiene dos ba y una sola ab. Elaborado por: Mario Zuluaga Tobón Cátedra de Compiladores Sitio Web del Curso: www.geocities.com/marioztobon

Documents

Cuadernillo de Ejercicios Sobre Automatas