Animador de autómatas finitos

Un autómata finito tiene memoria fija — su conjunto de estados. Sin importar cuán larga sea la cadena de entrada, la máquina nunca usa más memoria que su número de estados. Por eso los AFD no pueden contar sin límite: no existe un estado que 'recuerde' un entero arbitrario. El lema del bombeo lo precisa: cualquier cadena suficientemente larga aceptada por un AFD puede tener una sección intermedia repetida un número arbitrario de veces y seguir siendo aceptada. Los lenguajes que no se pueden bombear (como aⁿbⁿ, igual cantidad de a y b) necesitan un autómata de pila o una máquina de Turing. El teorema de Myhill-Nerode da el mínimo exacto: el número de estados equivale al número de clases de equivalencia distinguibles de los prefijos de entrada.

Un autómata finito determinista es simplemente un diagrama etiquetado de estados unidos por flechas. Para cada estado y cada símbolo de entrada existe exactamente una flecha a seguir, así que nunca hay que elegir: la máquina lee la cadena una sola vez, de izquierda a derecha, y termina en un único estado. Si ese estado final está marcado como de aceptación, la entrada pertenece al lenguaje. Seguirlo es tan fácil como deslizar una ficha por las flechas, que es justo lo que muestra esta herramienta.

Los autómatas finitos no surgieron en la informática. En 1943 Warren McCulloch y Walter Pitts describieron las neuronas como simples unidades de encendido/apagado conectadas entre sí, y esto se convirtió en el primer modelo matemático de una máquina de estados finitos. En 1951 Stephen Kleene analizó qué patrones podían reconocer esas 'redes nerviosas' y los llamó eventos regulares, el origen de las expresiones regulares actuales. Así que el autómata que recorres desciende directamente de un intento de explicar cómo calcula el cerebro.