Unidad 3

DIVISIÓN.
INGENIERÍA EN SISTEMAS COMPUTACIONES
GRUPO.
352-M
ASIGNATURA.
LENGUAJES Y AUTÓMATAS 1
DOCENTE.
SANTILLAN CHOREÑO MARIA ANGELICA
NOMBRE DEL ALUMNO.
NO. DE CONTROL.
FECHA
Nº ACTIVIDAD

SERRANO IZAGUIRRE LUIS ANGEL
VILLANUEVA ZAMORA DAVID FERNANDO
HERNÁNDEZ ESPINDOLA FRANCISCO JAVIER

123107145
123107119
123107154



PRODUCTO.
UNIDAD 3: AUTOMATAS FINITOS
CALIFICACIÓN Y FIRMA DELPROFESOR.


Unidad 3
AUTOMATAS FINITOS

Temario:
3.1 DEFINICIÓN FORMAL 2
3.2 CLASIFICACIÓN DE AUTÓMATAS FINITOS 2
3.3 CONVERSION DE UN AUTOMATA FINITO NO DETERMINISTA A UN AUTOMATA FINITO DETERMINISTA 4
3.4 REPRESENTACIÓN DE ER USANDO AFND 5
3.5 MINIMIZACIÓN DE ESTADOS EN UN AF 8
3.6 APLICACIONES 9
REFERENCIAS BIBLIOGRÁFICAS 10





3.1 DEFINICIÓN FORMAL
El Autómata Finito es la máquina másrestrictiva de todas y desde luego que se puede definir como un caso particular de una MT. También podemos verla como un AP sin pila. Obviamente que al sacarle la pila lo único que queda es la cinta finita de entrada. Este modelo matemático abstracto representa la solución del problema de aceptación de lenguajes de tipo 3 o LR.

Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:
 esun conjunto finito de estados;
  es un alfabeto finito;
  es el estado inicial;
 es una función de transición;
 es un conjunto de estados finales o de aceptación.

3.2 CLASIFICACIÓN DE AUTÓMATAS FINITOS
AUTÓMATA FINITO DETERMINISTA:
Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre elautómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).
En un AFD no pueden darse ninguno de estos dos casos:
Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
Que existan transiciones del tipo δ(q, ε), salvo que q sea un estado final, sin transiciones hacia otros estados. Un ejemplo interesante de autómatasfinitos deterministas son los tries.

AUTÓMATA FINITO NO DETERMINISTA
Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitos deterministas, 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.
Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
Queexistan 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ómatacambiar de estado sin procesar ningún símbolo de entrada.
Formalmente, se distingue de la 5-tupla que define a un autómata finito determinista en su función de transición. Mientras en un AFD esta función se define de la siguiente manera:

en un AFND se define como:

Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:

donde P(Q) es el conjunto potencia de Q.
Estosignifica que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que Q pertenece al conjunto P(Q).
La interpretación que se suele hacer en el cómputo de un AFND es que el autómata puede estar en varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Otra interpretación puede ser imaginar que la máquina"adivina" a qué estado debe ir, eligiendo una transición entre varias posibles. Note finalmente que en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial, relajando aún más la definición original.

3.3 CONVERSION DE UN AUTOMATA FINITO NO DETERMINISTA A UN AUTOMATA FINITO DETERMINISTA

Todo AFND (QN, Σ, q0, δN, FN) puede convertirse en un AFD (QD, Σ, q0,...