viernes, 24 de febrero de 2012

Autómatas Deterministas



Existen dos grandes grupos de autómatas, los autómatas deterministas y los no deterministas. Aunque antes de hablar de éstos, hay que definir lo que es un autómata finito, también llamado máquina de estado finito, que es una máquina computacional que realiza operaciones con una entrada para intentar proporcionar una salida. Esta salida dependerá de las transacciones que se producen entre los diferentes estados según se va analizando la entrada.

Un autómata finito determinista, es por tanto un autómata finito, que además tiene la restricción de que, partiendo de un estado, éste únicamente puede tener una transacción a otro estado utilizando un símbolo concreto. Existen procesos de minimización para conseguir transformar un autómata no determinista en determinista, ya que todos los AFND(Autómatas finitos no deterministas) tiene un AFD(Autómatas finitos deterministas) asociado. Esta operación de minimización simplifica el autómata y produce un automáta que al ser el resultado de la minimización, es más eficiente que el anterior.


AF Deterministas, AFD’s: se definen mediante una quíntupla ( E, Q, f, q0, F), donde:

- E: alfabeto de entrada.
- Q: conjunto de estados, es conjunto finito no vacío, realmente un alfabeto para distinguir a los estados.
- f: Q x Q, función de transición.
- q0 Q, estado inicial.
- F Q: conjunto de estados finales o de aceptación.


AFD como reconocedor de un Lenguaje:

• Cuando un AF transita desde q0 a un estado final en varios movimientos, se ha producido el RECONOCIMIENTO o ACEPTACIÓN de la cadena de entrada.
• Cuando un AF no es capaz de alcanzar un estado final, se dice que el AF NO RECONOCE la cadena de entrada y que ésta NO PERTENECE al lenguaje reconocido por el AF.

Automata finito determinista
Automata Finito Determinista

Lenguaje asociado a un AFD:

- Sea un AFD = (Σ, Q, f, q0, F), se dice que una palabra x es aceptada o reconocida por el AFD si f’(q0,x) F.
- Se llama lenguaje asociado a un AFD al conjunto de todas las palabras aceptadas por éste.


Es posible tener varios autómatas que reconozcan el mismo lenguaje. Para todo autómata que tiene otro con de la misma equivalencia (i.e. reconoce el mismo lenguaje) donde el número de estadosdel autómata sea el mínimo.

Se dispone de un descriptor del lenguaje (lenguaje regular): gramática tipo 3, AFD, AFND, expresión regular. Se plantean problemas de decisión:

• ¿El lenguaje descrito es vacío?
• ¿Existe una determinada cadena w en el lenguaje descrito?
• ¿Dos descripciones de un lenguaje describen realmente el mismo lenguaje? Nota: usualmente los lenguajes son infinitos, con lo que no es posible plantear la pregunta y recorrer el conjunto INFINITO de cadenas.


Autómatas con la misma equivalencia
1.- Estados de automatas con la misma equivalencia  en AFD’s distintos:

- Sean 2 AFD’s: ( ,Q,f,q0,F) y ( ’,Q’,f’’q0’,F’)
- los estados p,q / p Q y q Q’ son de la misma equivalencia (pEq) si se verifica que f(p,x) F f”(q,x) F’ x E*
2.- Estados de equivalencia en AFD’s distintos:
- Dos AFD’s tienen equivalencia si reconocen el mismo lenguaje, es decir: Si f(q0,x) F f(q0’,x) F’ x E*.
- Dos AFD’s  tienen equivalencia  si lo son sus estados iniciales: q0 E q0

No hay comentarios:

Publicar un comentario en la entrada