Teoría de autómatas

Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés).

En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados unos determinados estado y símbolo.

La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.

Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por sí mismo.

Existen tres tipos de autómatas finitos Sin embargo, puede observarse que todos estos tipos de autómatas pueden aceptar los mismos lenguajes.