unidad 3

TECNOLÓGICO DE ESTUDIOS SUPERIORES DE
CUAUTITLÁN IZCALLI
Código: FO-205P11000-XX
FORMATO DE ENTREGA
DE EVIDENCIAS
Página 1de6

DIVISIÓN.

INGENIERÍA EN SISTEMAS COMPUTACIONES

ASIGNATURA.

LENGUAJES Y AUTÓMATAS I

NOMBRE DEL ALUMNO.
Ramirez Muñoz Victor
Rodríguez Ugalde Jesús Humberto
PRODUCTO.

DOCENTE.
NO. DE CONTROL.
123107160
123107140

GRUPO.

351-m

-Santillán Choreño María Angélica
FECHANº ACTIVIDAD

CALIFICACIÓN Y FIRMA
DEL PROFESOR.

Unidad III

INDICE

3.1 Definición formal……………………………………………………………………...2
3.2 Clasificación de autómatas finitos………………………………………………….2
3.3 Conversión de un autómata finito no determinista a autómata finito
determinista (AFN-AFD)…………………………………………… …………………….3
3.4 Representación de expresión regular usando autómatas finitos no deterministas (ERAFND)……………………………………………………………………………………….4
3.5 Minimización de estados en un autómata finito (AF)………………………………4
3.6 Aplicaciones (Definición de un caso de estudio)…………………………………..5
Bibliografía………………………………………………………………………………….6

TECNOLÓGICO DE ESTUDIOS SUPERIORES DE
CUAUTITLÁN IZCALLI
Código: FO-205P11000-XX
FORMATO DE ENTREGA
DE EVIDENCIAS
Página 2de6

UNIDAD III
AUTOMATAS FINITOS

3.1 Definición formal
Un autómata finitoes un vector de tres elementos
M = (I, S ,δ, F)
Donde I es el conjunto finito de entradas, S es el conjunto finito de estados (no vacío), δ es
la función de transición de estados y F es el conjunto finito de estados finales (incluidos en
S).
El hecho de que todos los conjuntos sean finitos, le otorga a este elemento el atributo de
finito.
También se puede desprender de la definición que unautómata finito es un tipo especial
de máquina secuencial, en la cual no existen señales de salida como tal sino que sólo hay
señales de entrada y estado, como sucedía en la máquina de Moore.
Debido a este motivo, las máquinas secuenciales cumplen todos los axiomas de los automatas finitos. Siendo ésta la razón por
3.2 Clasificación de autómatas finitos
– Determinista (AFD): el autómata no puede estar enmás de un estado simultáneamente
– No determinista (AFN): puede estar en varios estados al mismo tiempo
• No determinismo
– no añade ningún lenguaje a los ya definidos por los AFD
– aumento de la eficiencia en la descripción de una aplicación
Determinista: para cada entrada, existe un único estado al que el autómata puede llegar
partiendo del estado actual
• Consta de:
– un conjunto finito deestados, Q
– un conjunto finito de símbolos de entrada, Σ
– una función de transición ( δ) que, dados un estado y una entrada, devuelve un estado.
δ(q, a) = p

TECNOLÓGICO DE ESTUDIOS SUPERIORES DE
CUAUTITLÁN IZCALLI
Código: FO-205P11000-XX
FORMATO DE ENTREGA
DE EVIDENCIAS
Página 3de6

– un estado inicial (uno de los estados de Q), q 0 – un conjunto de estados finales o de
aceptación (subconjunto deQ), F• A = (Q, Σ, δ, q0, F)
3.3 Conversión de un autómata finito no determinista a autómata finito determinista
(AFND-AFD)
El estado inicial del AFD será S0 y los estados finales serán todos aquellos Si que
contengan al estado final del AFN original.
La función de transición es el resultado de todas las operaciones Ir_A sobre los Si.
Se calcula la C_ε del estado inicial del AFN, el resultado seráel estado inicial S0 del AFD.
•S0 será el estado inicial del AFD y el primer Si del AFD.
2. Se calcula para cada Si la operación Ir_A para cada α ϵ Σ, la cual arrojara un estado
Si (Pudiendo repetirse).
3. Se realiza la operación 2 con todos los estados hasta que ya no surjan estados
diferentes.
3.4 Representación de expresión regular usando autómatas finitos no deterministas
(ER-AFND)
Existenalgoritmos que relacionan la especificación de tokens -expresiones regulares-,
con el reconocimiento de éstos -autómatas finitos-. Es posible dada una expresión
regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la
expresión regular. También es posible obtener el AFND que reconozca el lenguaje
representado por dicha expresión regular.
El algoritmo que permite...