taller automatas finitos

TALLER DE EXPRESIONES REGULARES Y AUTOMATAS FINITOS



FUNDACIÓN UNIVERSITARIA DE POPAYAN
INGENIERIA DE SISTEMAS
Popayán, 17 de marzo de 2013


Taller de Expresiones Regulares yAutómatas Finitos
1. Sea Σ = (x, y), escriba una expresión regular que genere el lenguaje de todas las palabras que comienzan con una x y que es seguida de dos o tres y.
R/ta ER = X (YY | YYY)
2.Sea Σ = (x, y), escriba una expresión regular que genere todas las palabras de longitud 5 que comienzan con una x y terminan con una y.
R/ta ER = X (X|Y)*(X|Y)*(X|Y)* Y
3. Compruebe que lasER 1(0|1)(0|1)1 y 1001|1011|1101|1111 son equivalentes.

R/ta en la expresión 1(0|1)(0|1)1 hay un 1 al comienzo y al final, lo que permite generar las siguientes combinaciones

1(0|1)10 | 11
(0|1)1 01 | 11

1001 | 1011 | 1101 | 1111. Por lo tanto son equivalentes.
4. Describa, mediante una frase, al lenguaje del ejerció anterior.

R/ta “Todos los númerosbinarios de longitud 4 que comienzan con un 1 y terminan con un 1”.
5. Sea la ER 101101 | 1001101 | 1001. Obtenga una ER más compacta que sea equivalen te a esta expresión.

R/ta ER = 10(11 | 011 |ε ) 01
6. Escriba una expresión que represente al lenguaje todas las palabras sobre el alfabeto {0,1} que tienen exactamente tres 0s

R/ta ER = 1* 01* 01* 01*






7. Construya unDFA que reconozca el lenguaje X (XY)*

R/ta


8. Construya un DFA para todas las palabras sobre el alfabeto { X, Y, Z } que terminan con Y.

R/ta ER = (X | Y | Z)* Y
Diagrama de transición DFA Para la ER ( X | Y | Z)* Y










9. Repetir losejercicios 7 y 8 usando la construcción de Thompson

Ejercicio 7. X (XY)*





Ejercicio 8. ( X | Y | Z)* Y...