Teoria De La Comutacion

Problemas para el último corte (Unidad 3 y Unidad 4) 1. Dibujar el diagrama de transición de la Máquina de Estado Finito que corresponde a cada inciso, además de expresar los seis conjuntos queforman la representación para M = (I, O, S, f, g, 0). a) I S  q0 q1 q2 a q1 q0 q2 f b q0 q1 q1 c q0 q2 q0 a z y x g b y x z c y w x

b) I S  A B C D x B A C D f y D C A D z B B D C x a d c d g y b a bc z a c b b

2. Determinar cuáles son los conjuntos que determinan la descripción formal para las siguientes Máquinas de Estado Finito, además de las tablas de transición para cada inciso. a) a/1 q0 b/0 b)  W q1 a/0 x/0 X x/1 b/1 a/1 b/1 q2

x/0

y/1 y/0 Y X/0

y/1

y/1

Z

3. Establecer las transiciones (estados y cadenas de salida) que resultan al introducir las siguientescadenas de entrada, referidas a las Máquinas de los problemas 1 y 2. a) babccab en 1a) b) zxyzxzyz en 1b) c) bbabbbaaba en 2a) d) xyxyyxyxxy en 2b).

4. Diseñar una Máquina de Estado Finito, quetambién sea Autómata de Estado Finito, con las siguientes características: I = {a, b, c}, S = {A, B, C, D}, 0 = {A}. 5. Dado el siguiente diagrama de transición determinar: a) ¿Se puede transformar estaMáquina en un Autómata Finito?

6. Diseñar un Autómata Finito con I = { a, b } que acepte cadenas con una cantidad impar de letras a. 7. Diseñar un Autómata con las entradas I = { a, b } que acepte elsiguiente lenguaje: L={ba2(a, b)*} 8. Diseñar un Autómata que acepte el siguiente lenguaje regular : L={(0,1)* 101 (0,1)*} 9. Diseñar un Autómata que acepte el siguiente lenguaje regular : L={(0,1)*02}10. Diseñar un Autómata Finito que acepte cadenas no nulas formadas con los símbolos del conjunto I = { a, b, c } y que no contengan ni a ni c. 11. Diseñar un Autómata de Estado Finito que acepte lascadenas de bits con una cantidad de 0 igual a un múltiplo de 2 ó de 3. 12. Diseñar un Autómata Finito con I = { a, b } que acepte las palabras en las que siempre que aparezca una b, esté seguida...