Automata

AUTOMATAS FINITOS:
Los autómatas se pueden emplear como herramientas de diseños para buscar la primera concurrencia de una rutina. El proceso se termina cuando se encuentra la primera ocurrencia del patrón.

Autómatas finitos deterministas (DFA).
Un Autómata Finito Determinista consiste en un dispositivo que puede estar en cualquier estado entre un número finito, uno de loscuales es el estado inicial y por lo menos uno es un estado de aceptación. A este dispositivo está unido un flujo de entrada por medio del cual llegan en secuencia los símbolos de un alfabeto determinado. La máquina tiene capacidad para detectar los símbolos conforme llegan y, basándose en el estado actual y el símbolo recibido, ejecutar una transición consistente en cambiar a otro estado o lapermanencia en el mismo. El programa de un Autómata Finito Determinista no debe contener ambigüedades (para un estado un determinado símbolo sólo puede producir una determinada acción).
Se dice que un Autómata Finito Determinista acepta su cadena de entrada si, después de comenzar sus cálculos en el estado inicial la máquina cambia a un estado de aceptación después de leer el último símbolo dela cadena. Si después de leer el último símbolo no queda en estado de aceptación, se dice que la cadena ha sido rechazada. Si la entrada es una cadena vacía será aceptada si y sólo si el estado inicial es también un estado de aceptación. Un Autómata Finito Determinista consiste en una quíntupla (S,∑,∂,t, F) donde:
a. S, es un conjunto finito de estados.
b. , ∑ es el alfabeto de lamáquina.
c. , ∂ es una función (función de transición) de S×∑xS a S.
d., t (un elemento de S) es el estado inicial.
e. F (un subconjunto de S) es el conjunto de estados de aceptación.

La interpretación de la función de transición de un autómata finito determinista es que (p,x)=q sí y sólo sí la máquina puede pasar de un estado p a un estado q al leer el símbolo x.El diagrama de transición determinista sólo debe tener un arco que sale de un estado para cada símbolo del alfabeto. Además, dicho diagrama está completamente definido, es decir, debe existir un arco para cada símbolo del alfabeto.

Interpretación de un DFS como un mecanismo

A raíz de la descripción formal del concepto de DFA, debemos darle la interpretación en el campo de lainformática, ya que tiene un uso práctico derivado de los modelos abstractos del cálculo.

La interpretación de autómatas será como una maquina del tipo de los ordenadores. Los DFA son maquinas que están reducidas a unidades de control y a una cabeza que le cinta de entrada., que conta con memoria finita, siendo en el caso de una memoria de N bits de capacidad puede adoptar 2 sobre n.Lenguaje reconocido por un FDA. Finitos deterministas.

LENGUAJES REGULARES
Se define Σ* como el conjunto de cadenas de longitud finita formadas por el alfabeto Σ. Un subconjunto de Σ * se denomina lenguaje. Si M es un autómata finito determinista ( S, Σ, δ, ι, F), la colección de cadenas que acepta constituye un lenguaje con respecto al alfabeto Σ. Este leguaje se representacomo L(M), que es el lenguaje que acepta el autómata M. Un lenguaje de la forma L(M) para un autómata finito M se denomina lenguaje regular.

TEOREMA

Para cualquier alfabeto S, existe un lenguaje que no es igual a L(M) para cualquier autómata finito determinista M.

Demostración.

Puesto que cualquier arco de un autómata finito determinista que esté rotulado con unsímbolo que no pertenece a no tendrá efecto alguno sobre el procesamiento de una cadena en , podemos considerar sólo las máquinas con alfabeto . Sin embargo, la colección de autómatas finitos deterministas con alfabeto es contable ya que podemos elaborar de forma sistemática una lista de todas las máquinas posibles con un estado, seguidas por todas las máquinas con dos estados, luego las de tres...