MEF

MAQUINAS DE ESTADO FINITO

DEFINICIÓN:

modelos de comportamiento de un sistema o un objeto complejo, con un número limitado de modos o condiciones predefinidos, donde existen transiciones de modo.

modelo matemático que realiza computos de forma automática sobre una entrada para producir una salida

Se utiliza porque:

• Resuelve la mayoría de los problemas en el análisis léxico.
• Consumen una cantidad fija de memoria.
• Son muy eficientes.
• Existe una teoría matemática que da sustento y permite modificarlos.:

Una MEF consta de:

• Un conjunto finito de símbolos de entrada.
• Un conjunto finito de estados
• Uno o más estados definidos como estado inicial
• Uno o más estados definidos como estados de aceptación
• Un conjunto de transiciones.
• Una transición es una función que determina el nuevo estado en que quedará la MEF, con base en el estado actual y el símbolo de entrada.

UTÓMATAS FINITOS

 La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

CLASES DE AUTÓMATAS FINITO

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 el autó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ómatas finitos deterministas son los tries.

AUTÓMATA FINITO NO DETERMINISTA:

Haciendo la analogía con los AFDs, 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;  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.  Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

VÍDEO DE AUTÓMATAS:

REFERENCIAS:

Libro Compiladores: principios, técnicas y herramientas

 Escrito por Alfred V. Aho,Ravi Sethi,Jeffrey D. Ullman

Compiladores.pdf-adobe ReaderCorporación Universitaria Remington – Dirección Pedagógica

http://es.wikipedia.org/wiki/Aut%C3%B3mata_(mec%C3%A1nico)