Animador de autómatas finitos

recorre las transiciones de un AFD en un diagrama de estados en vivo

Ejemplo resuelto — Animador de autómatas finitos

Siguiente símbolo	'1'

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

memoria finita, cadenas infinitas 🖖

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.

una ficha, un camino 🖖

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.

nacido de un modelo de neuronas 🖖

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.

Problema resuelto al detalle

Por qué ninguna máquina finita puede emparejar 0 y 1, por muchos estados que se le den 8 pasos
La máquina de paridad de esta página tiene dos estados y lee 101101, seis símbolos, sin necesitar jamás un tercero. Entréguele seis millones de símbolos y seguirá necesitando dos. ¿Qué es lo que no puede hacer una máquina con un número fijo de estados? ¿Y cómo se demuestra que una máquina no existe, en lugar de haber fallado simplemente al buscar una?
1. Observe la máquina que tiene. La paridad comienza en e, y cada 1 la conmuta. Seis símbolos después está de nuevo en e y la entrada es aceptada. No se ha acumulado nada por el camino: en el símbolo seis, la máquina se encuentra exactamente en la misma condición en la que podría haber estado en el símbolo uno.
  
  $e 1 o 0 o 1 e 1 o 0 o 1 e$
2. Ese es todo el recurso de que dispone. La memoria de un DFA es el estado en el que se encuentra y nada más. Ni contador, ni pila, ni cinta en la que pueda escribir. Tras leer cualquier prefijo, todo lo que la máquina sabe sobre ese prefijo es cuál de sus k estados ocupa ahora.
  
  $∣ Q ∣ = k ⟹ at most k distinguishable pasts$
3. Busque pues algo que claramente requiera más. Considere las cadenas formadas por un cierto número de ceros seguidos exactamente por el mismo número de unos. 01 es una, 0011 es una, 001 no lo es, ni tampoco 0110.
  
  $L = {0^{n} 1^{n} : n \geq 0}$
4. Suponga que un DFA con k estados lo reconoce. No pregunte qué aspecto tiene la máquina: nadie se lo va a decir. Limítese a introducir los k+1 prefijos formados por entre 0 y k ceros, y observe en qué estado la deja cada uno.
  
  $0^{0}, 0^{1}, \dots, 0^{k} ⟶ k + 1 strings into k states$
5. Principio del palomar. Hay más prefijos que estados, de modo que dos de ellos van a parar al mismo sitio. Llámelos 0ⁱ y 0ʲ con i menor que j. A partir de ese momento, la máquina no puede distinguirlos, y no porque esté mal diseñada. El estado es todo lo que tiene, y las dos cadenas le dieron el mismo.
  
  $δ^{*} (q_{0}, 0^{i}) = δ^{*} (q_{0}, 0^{j}), i < j \leq k$
6. Ahora introduzca en ambas continuaciones lo mismo: i unos. Mismo estado inicial, mismos símbolos, luego mismo estado final y, por tanto, el mismo veredicto. La máquina no tiene margen para hacer ninguna otra cosa.
  
  $δ^{*} (q_{0}, 0^{i} 1^{i}) = δ^{*} (q_{0}, 0^{j} 1^{i})$
7. Y ambos veredictos tienen que diferir. 0ⁱ1ⁱ tiene recuentos coincidentes y pertenece al lenguaje; 0ʲ1ⁱ no, porque j no es i. Una debe ser aceptada y la otra rechazada, y la máquina les da la misma respuesta. Lo que falla es la suposición de que existía.
  
  $0^{i} 1^{i} \in L, 0^{j} 1^{i} \in / L$
8. Relea el argumento y observe lo que nunca ha aparecido en él: un valor para k. Dos (el tamaño de la propia máquina de paridad) o dos mil millones: los k+1 prefijos superan en número a los k estados en cualquier caso. Sin embargo, si impone un límite a n, el lenguaje pasa a ser de estados finitos inmediatamente: emparejar hasta N requiere 2N+2 estados, es decir, 22 para N = 10 y 202 para N = 100.
  
  ${0^{n} 1^{n} : n \leq N} needs 2 N + 2 states$
Respuesta

Ningún autómata finito lo reconoce, sea cual sea su tamaño. La demostración no necesita saber nada sobre cómo está construida la máquina, solo que k+1 elementos no pueden caber en k lugares sin que dos de ellos compartan sitio, y que compartir estado es olvidar. La máquina de paridad muestra lo mismo en miniatura: introdúzcale 0, luego 00 y después 000, y las tres la dejan en e, porque no examina los ceros en absoluto.

En el límite reside toda la dificultad. Emparejar hasta N es fácil, con 2N+2 estados, un par más por cada símbolo al que se desee llegar, y ese recuento crece sin parar, por lo que cada N en particular tiene una máquina y ninguna máquina abarca todo N. Esa brecha es lo que significa «memoria finita», y es la razón por la cual el siguiente paso tras un DFA se define dotándolo de una pila: un almacenamiento no acotado, añadido de nuevo precisamente porque esto es lo que cuesta su ausencia.

Referencias (2)

Insight block 3 — the nerve-net model the finite automaton descends from: W. S. McCulloch and W. Pitts, "A logical calculus of the ideas immanent in nervous activity." Bulletin of Mathematical Biophysics 5(4), 115–133, 1943.
Insight block 1 — the theorem that fixes the minimum state count: A. Nerode, "Linear automaton transformations." Proceedings of the American Mathematical Society 9(4), 541–544, 1958.

Por el equipo de 42Math · Actualizado 2026-06-03

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

termina en 01 - El reconocedor de sufijos acepta cadenas que terminan en 01.
rechazada (termina en 10) - Avanza hasta el final y la máquina termina en q1 y rechaza, habiendo pasado por el estado de aceptación q2 a mitad de camino. Leer un 01 en algún punto del medio no es lo mismo que terminar con uno. Toda la respuesta de un AFD es el estado tras el último símbolo, y carece de medios para recordar que alguna vez estuvo en un sitio mejor.
cantidad par de unos ✓ - El autómata de paridad acepta cadenas binarias con un número par de unos.
cantidad impar de unos ✗ - Tres 1 en la entrada, y la máquina de paridad cambia de estado con cada uno: e, o, o, e, o. Termina en o y rechaza. Aquí no se cuenta nada. Dos estados es todo lo que tiene y todo lo que necesita, porque saber si la cuenta hasta el momento es impar es el único dato que merece la pena recordar sobre una cadena de cualquier longitud.
contiene 101 ✓ - La máquina llega a s3 en el cuarto símbolo y luego no puede salir: s3 lleva a s3 tanto con un 0 como con un 1. Pasan tres símbolos más y el veredicto ya está fijado para todos. Un estado trampa es el modo en que un AFD se compromete con el sí antes de agotar la entrada, sin registrar nada sobre cuándo pasó.
sin 101 ✗ - Rechaza en s2, lo que la leyenda llama «leído 10: a un símbolo de distancia». Un 1 más al final habría completado el patrón y bloqueado la máquina en s3 para siempre. El estado en el que acabas indica lo cerca que te quedaste, algo que el mero hecho de aceptar o rechazar jamás podría decirte.