Automatas

Que es?
La teoría de autómatas es la que se ocupa de clasificar y estudiar de modo sistemático diferentes tipos de máquinas abstractas que llevan a cabo un procesamiento secuencial de lainformación. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces dereconocer.
Autómatas Finitos.
Es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
Hay  tres tipos de autómatas finitos:
Autómata finitodeterminista
Autómata finito no determinista
Autómata finito nodeterminista
con transiciones.
Autómatas Finitos determinista.
Son máquinas teóricas que van cambiando de estado dependiendo de la entradaque reciban. La salida de estos Autómatas está limitada a dos valores: Aceptado y No Aceptado
Formalmente, un Autómata Finito Determinista
(AFD) se define como una tupla:
Σ = Es elalfabeto de entrada. q0 = Estado inicial
Q = Es el conjunto finito y no vacío de los estados
f = Es la función de transición F = Estado Final.

Autómatas Finitos NO determinista
Aquí podemosencontrarnos con varias opciones e, incluso, con λ-transiciones que se realizan sin considerar el correspondiente símbolo de la cadena de entrada. Para tener en cuenta estas consideraciones, los AFND sedefinen como una
tupla: AFND = (Σ, Q, f, q0, F, T), f : Q × Σ → 2Q
Σ = Es el alfabeto de entrada. q0 = Estado inicial
Q = Es el conjunto finito y no vacío de los estados
f = Es la función detransición F = Estado Final
2Q = Conjunto formado por los subconjuntos de Q
T = Relación binaria definida sobre Q que indica las λ-transiciones

Autómatas FinitosNO determinista con transiciones.Además de ser capaz de alcanzar más estados leyendo un símbolo, permite alcanzarlos sin leer ningún símbolo. Si un estado tiene transiciones etiquetadas con E, entonces el AFND puede encontrarse en...