Teoría de las Ciencias
Computacionales
Nombre del Estudiante, Matrícula y Grupo:
José Carlos Sánchez Parrilla
84473
CC24
Asesor Disciplinar: Dr. Gerson Villa González
Amecameca, Estado de México a 27 de Marzo de 2017
Diseño de un autómata finito con
transiciones vacías
Actividad de Aprendizaje 3
Introducción.-
Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a
diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q,
tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
En un AFND puede darse cualquiera de estos dos casos:
Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien
un estado final pero con transiciones hacia otros estados.
Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito
no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas
transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de
entrada. Considérese una modificación al modelo del autómata finito para permitirle
ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.
1.- Considera el alfabeto {M, D, C, L, X, V, I} y el lenguaje de los números
romanos. Demuestra que es un lenguaje regular construyendo un autómata finito con
transiciones vacías que lo reconozca. Recuerda que, por ejemplo, VIIII no es un
número romano, y que debemos escribir IX, en su lugar. Puede resultar útil construir
la expresión regular y luego el ε-AFND correspondiente.
Letras: I V X L C D M
Valores: 1 5 10 50 100 500 1000
Reglas del sistema de numeración romano:
Si a la derecha de una cifra romana se escribe otra igual o menor, el valor de ésta
se suma a la anterior.
Ejemplos: VI = 6; XXI = 21; LXVII = 67
La cifra "I" precediendo a la "V" o la "X", les resta una unidad; la "X", precediendo a
la "L" o a la "C", les resta diez unidades y la "C", precediendo a la "D" o la "M", les
resta cien unidades.
Ejemplos: IV = 4; IX = 9; XL = 40; XC = 90; CD = 400; CM = 900
En ningún número se puede poner una misma letra más de tres veces seguidas.
Ejemplos: XIII = 13; XIV = 14; XXXIII = 33; XXXIV = 34
La "V", la "L" y la "D" no pueden duplicarse porque otras letras ("X", "C", "M")
representan su valor duplicado.
Ejemplos: X = 10; C = 100; M = 1.000
Si entre dos cifras cualesquiera existe otra menor, ésta restará su valor a la
siguiente.
Ejemplos: XIX = 19; LIV = 54; CXXIX = 129
En base a estas reglas, se dibuja el grafo del autómata en JFlap:
Definiendo el quíntuplo:
Q={q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15,q16,q17,q18,q19,q20,q2
1,q22,q23,q24,q25,q26,q27,q28,q29}
Σ={M, D, C, L, X, V, I}
δ= Q x (Σ ∪ {ε})
q0=q0
F={q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q16,q18,q19,q20,q21,q22,q23,q2
4,q25,q26,q27}
Realizando algunas pruebas
Referencias
Rajeev Motwani, Jeffrey D. Ullman. Introducción a la Teoría de Autómatas
Lenguajes y Computación.
Hopcroft, J. E., Motwani, R., Ullman, J. D. Teoría de autómatas, lenguajes y
computación.
kelley D. (1995). Teoría de autómatas y lenguajes formales
Pozo J. (1993). Teorías cognitivas del aprendizaje
Sipser M. (1997).Introduction of the theory of the computation
Sudkamp T. (1994). Languages and machines
Brena, R. Autómatas y Lenguajes (2003).Instituto Tecnólogico y de Estudios
Superiores de Monterrey. 4. JFLAP Tutorial. Recuperado de
http://www.jflap.org/tutorial/
