Instituto de Estudios Universitarios

Jazmín Contreras Gómez

Matricula: 68976

Grupo: CC14

“Teoría de las Ciencias Computacionales”

Dra. Lilian Dinorah Coronado de Alba

Actividad 3:
“Diseño de un Autómata Finito con Transiciones Vacías”

Comalcalco, Tabasco. 21 de Agosto de 2015.

DISEÑO DE UN AUTÓMATA CON TRANSICIONES VACÍAS

El objetivo de esta actividad es generar autómatas con transiciones vacías para reconocer lenguajes regulares, pero antes se define el siguiente concepto: Un autómata finito no-determinista con transiciones ε es un quíntuplo (Q, Σ, δ, q0, F) con todos sus componentes como se han definido hasta ahora, pero la δ, la función de transición, transforma Q x …ver más…

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, resultando:

Figura 1. Grafo de Autómata finito no determinista con transiciones vacías ε-AFND, donde λ= ε.

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,q21,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,q24,q25,q26,q27}
A continuación se muestran algunos ejemplos de las cadenas que el autómata acepta, estos ejemplos son los que demuestran las reglas del sistema de numeración romano.

Figura 2. Grafo de ε-AFND, con cadenas que acepta el autómata.

Figura 3. Grafo de ε-AFND, con cadenas que acepta el autómata y cadenas que no acepta.
Conclusión
Rajeev Motwani, Jeffrey D. Ullman en Introducción a la Teoría de Autómatas Lenguajes y Computación. 2002, definen que los Lenguajes Regulares son lenguajes formales que tienen estas características:
1. Puede ser