Las máquinas de estados Finitos(autómatas finitos) conocidas como Finite State Machines por su traducción al Inglés, nos sirven para realizar procesos bien definidos en un tiempo discreto. Reciben una entrada, hacen un proceso y nos entregan una salida. Notemos que éstas máquinas hacen una computación.
En otras palabras, imaginemos una máquina capaz de seguir una secuencia finita de pasos al introducir un conjunto de datos en ella, solo se puede leer un dato en cada paso que se realice, por tanto el número de pasos a seguir está dado por el número de datos a introducir. Cada entrada diferente genera una salida diferente, pero siempre el mismo resultado con los mismos datos de entrada.
Por lo tanto una computación es capaz de resolver un problema, sí y solo sí tiene una solución algorítmica, es decir, puede ser descrito mediante una secuencia finita de pasos bien definidos.
Mediante una computación podemos encontrar soluciones a problemas que teóricamente tienen una representación algorítmica, pero que pueden necesitar tal cantidad de recursos (factores como el tiempo y el espacio de almacenamiento) que desde el punto de vista práctico no se puede llegar a la solución.
Estas máquinas pueden usarse para reconocer lenguajes. Es decir, para leer cadenas (secuencias de símbolos) y determinar si pertenecen o no a un lenguaje. Los autómatas también sirven para describir el comportamiento de otras máquinas o sistemas. En este caso, no siempre se usa el concepto de cinta de entrada. En lugar de esto el autómata responde a ciertas acciones o estímulos del mundo exterior. Esto no hace que el modelo sea más general ya que podemos pensar en que las acciones se codifican y se ponen en la cinta de entrada que podría inclusive tener una entrada infinita.
Se puede representar un autómata con un multi-grafo1. Cada nodo representa un estado, los arcos representan transiciones y están etiquetados con la acción (o con el símbolo leído de la cinta de entrada) que causa la transición. Se debe tener también una convención para indicar los estados donde puede comenzar la ejecución.
Los Autómatas se clasifican en 2 tipos: Autómata Finito Determinista y Autómata Finito no Determinista.
Autómatas Finitos Deterministas. Un Autómata recibe secuencialmente una cadena de símbolos y cambia de estado por cada símbolo leído o también puede permanecer en el mismo estado. Al final de la lectura el estado del Autómata nos indica si la cadena es aceptada o mejor dicho pertenece al Lenguaje que describe nuestra máquina. Si al final de leer todos los símbolos de entrada la máquina está en alguno de los estados Finales entonces esa cadena es aceptada, si el estado no es final entonces la cadena no pertenece al lenguaje.
Autómatas Finitos No Deterministas A diferencia de los Autómatas Finitos Deterministas, donde existe una única forma de llegar de un estado a otro con una entrada y se tiene solo un estado inicial, los Autómatas Finitos No Deterministas no cuentan con estas virtudes, pero son una herramienta de mucha ayuda cuando queremos diseñar un Autómata Determinista. Para cada Autómata No Determinista existe un Autómata Determinista que lo representa y que acepta el mismo lenguaje.
