Compiladores

AUTOMATA:
Un autómata o máquina de estado es el modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que elautómata reconoce valiéndose de estados.


















AUTÓMATA FINITO DETERMINISTA
Un autómata finito determinista (abreviado AFD) es un autómata finito que además es unsistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con esesímbolo.
Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:1
• es un conjunto de estados;
• es un alfabeto;
• es el estado inicial;
• es una función de transición;
• es un conjuntode estados finales o de aceptación.
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 transicionesdel tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.
Autómatas finitos deterministas (AFD)
Un autómata finito determinista (AFD) es unaquíntupla


donde
• es un alfabeto (sabemos )
• es un conjunto finito no vacío de estados, es decir, .
• es una función de transición:

Ejemplo: El lenguaje que acepta el DFA estaformado por todas las cadenas sobre el alfabeto S = {a, b}, siempre y cuando terminen con a.

Figura 2.1.
Q = {q0, q1}, S = {a, b}, q0 = q0 , F = {q1} y d se define mediante la tabla de la figura2.1.
Se puede utilizar también la siguiente lista para definir la función d
(q0, a) = q1(q0, b) = q0
(q1, a) = q1(q1 ,b) = q0
El diagrama de transición se muestra en la figura 2.2.
Para ver elgráfico seleccione la opción "Descargar" del menú superior
Consideremos otro ejemplo. El DFA M= {Q, S , q0, F, d } acepta el lenguaje L(M)={w Î {a, b}* que no contiene tres b’s consecutivas} y esta...