automatas

Autómatas Finitos
Autómatas Finitos Deterministas
Se llama Autómata Finito Determinista (AFD) a la quíntupla:
(, Q, f, q0, F)
 es un alfabeto, llamado “alfabeto de entrada”.
Q es un conjuntofinito, no vacío llamado “conjunto de estados”.
f es una función f: Qx  Q que se llama “función de transición”.
q0Q es el “estado inicial”.
FQ es el conjunto de “estados finales”, o “estadosde aceptación”, no vacío.

Un AFD puede considerarse como una máquina secuencial de Moore, cuyo alfabeto de entrada sea, su alfabeto de salida S=0,1, y donde F será el conjunto de los estadostales que g(q)=1.

Tabla de Transición

Será una tabla cuyas filas están encabezadas por los estados (elementos de Q). Los encabezamientos de las columnas son los símbolos del alfabeto de entrada(los elementos de). Cumpliéndose que el elemento i, j de la tabla de transición corresponde al valor de f (qi, ej), donde qi es el elemento i-ésimo de Q, y ej es el elemento j-ésimo de. Tanto elestado inicial como el final estarán marcados por  y por * respectivamente. Nota: el estado final puede ser indicado también rodeando el estado por un círculo.


(): a1...an
q0
.....
qi
......*qf


Ejemplo:
AF=(0,1,q0,q1,q2, f, q0, q1 )

f
0
1
q0
q1
q0
*q1
q0
q2
q2
q1
-

Diagrama de Transición
Es un grafo dirigido que se forma de la siguiente manera:
1. Elgrafo tendrá tantos nodos como Q, cada nodo estará etiquetado por un elemento de Q.
2. Si f(qi, ej) = qk, dibujaremos una rama dirigida desde el nodo de etiqueta qi hasta el nodo de etiqueta qk. Laetqueta de la rma será ej.
3. El estado inicial estará señalado mediante el símbolo .
4. Los estados finales estarán señalados mediante el símbolo *, o doble círculo alrededor de la etiqueta delestado final.
Representamos los estados como:



Ejemplo: (partiendo del autómata anterior)


Lenguaje asociado a un autómata finito determinista L(AFD)
Sea un AFD (, Q, f, q0, F). Decimos...