Si sabe describir su problema como un lenguaje, le decimos qué máquina lo resuelve.
Todo problema de «reconocer» algo —una cifra válida, una palabra, una frase bien construida, un patrón— puede verse como un lenguaje: un conjunto de palabras formadas con un alfabeto y unas reglas. Según la memoria que exijan esas reglas, la solución la da un autómata finito, un autómata de pila o una máquina de Turing… o no existe.
¿Qué computamos?
🔢 Cifras
Sumar 1 en binario, sumar en unario, pasar de binario a unario, múltiplos de 3.
🔤 Letras
Palíndromos (ABBA), aⁿbⁿ, aⁿbⁿcⁿ, ordenar letras, copiar una palabra.
🧩 Palabras y símbolos
Paréntesis equilibrados, expresiones aritméticas con su precedencia, identificación por ejemplos.
💬 Frases
Gramática del español (sujeto + predicado) con árbol sintáctico y reglas de transformación de frases.
La escalera de las máquinas (jerarquía de Chomsky)
| Si su problema necesita… | Lenguaje | Máquina | ¿Solución? | Ejemplo |
|---|---|---|---|---|
| Recordar solo una cantidad fija de información | Regular · tipo 3 | Autómata finito | Sí, siempre y en tiempo lineal | ¿Termina en «ción»? ¿Es múltiplo de 3 en binario? |
| Emparejar cosas anidadas o en espejo | Libre de contexto · tipo 2 | Autómata de pila | Sí, siempre | Paréntesis, ABBA, aⁿbⁿ, frases |
| Comparar tres o más partes, o copias exactas | Sensible al contexto · tipo 1 | Turing con cinta acotada | Sí, aunque puede ser costoso | aⁿbⁿcⁿ, ww |
| Memoria y pasos ilimitados | Recursivamente enumerable · tipo 0 | Máquina de Turing | Si hay algoritmo que termine; si no, solo «semidecidible» | Calcular, transformar, buscar |
| Predecir el comportamiento de cualquier programa | Indecidible | Ninguna | No (Turing, 1936) | ¿Terminará este programa? |
Cómo traducir su problema a un lenguaje
| Elemento del lenguaje | Pregunta para su problema | Ejemplo: «¿es un palíndromo?» |
|---|---|---|
| Alfabeto Σ | ¿Con qué símbolos trabaja? (cifras, letras, palabras…) | {A, B} |
| Palabras | ¿Qué es una entrada? ¿Cuáles son válidas y cuáles no? | ABBA ✔ · ABAB ✘ |
| Reglas | ¿Qué condición o transformación define lo válido? | S → A S A | B S B | A | B | ε |
| Memoria | ¿Cuánto hay que recordar mientras se lee? | La primera mitad entera → hace falta una pila |
| Estados de aceptación («de satisfacción») | ¿Cuándo damos la entrada por buena? | Cuando se han tachado todos los pares sin discrepancias |
Diagnóstico de su problema
Marque lo que necesita su problema. Si no marca nada, basta con memoria fija (lenguaje regular).
Identificador de lenguajes por ejemplos
Escriba palabras que su problema debe aceptar y otras que debe rechazar (una por línea; ε = palabra vacía). Las compararemos con un catálogo de lenguajes conocidos y le diremos cuáles encajan, de la máquina más sencilla a la más potente.
Los ejemplos nunca demuestran nada: solo descartan. Cuantos más y más variados, más fiable el resultado.
Programa
Formato: estado, lee -> nuevo, escribe, mueve con mueve = R (derecha) · L (izquierda) · S (quieto). Blanco: _. Si no hay transición, la máquina se detiene: acepta si está en un estado de aceptación y, si no, rechaza.
Tabla de transiciones δ
La fila resaltada es la transición que se acaba de aplicar.
Diagrama de estados
Doble círculo: aceptación · flecha naranja: estado inicial · etiquetas «lee/escribe movimiento» · el estado actual se resalta mientras la máquina funciona.
📦 Exportar y probar
Lleve esta máquina a su proyecto: código autónomo con la misma lógica del simulador.
Funciona en el navegador y en Node.js (sin dependencias).
Una regla por línea: A -> x B y | z | ε. Separe los símbolos con espacios. Los no terminales son los que aparecen a la izquierda; el primero es el inicial.
📦 Exportar y probar
Reconocedor autónomo (algoritmo de Earley) con su gramática incrustada.
Funciona en el navegador y en Node.js (sin dependencias).
patrón -> reemplazo sustituye la primera aparición; patrón ->. reemplazo sustituye y termina. ε = vacío. Use comillas para conservar espacios: "mi " -> "tu ". En cada paso se aplica la primera regla de la lista que encaje (algoritmo de Markov).
Usos profesionales
Pensar un problema como un lenguaje sirve para decidir qué tipo de solución necesita antes de programarla. Además, de esta web puede llevarse productos concretos:
De cada máquina y de cada gramática, sin dependencias.
Diagrama de estados y árbol de derivación para la documentación.
Baterías en CSV y JSON con el resultado esperado.
Comparta una máquina con un enlace que la abre ya cargada.
La herramienta trabaja a escala de diseño y prueba (entradas cortas, gramáticas pequeñas). Para producción, el código exportado es un buen punto de partida; en proyectos grandes se usan generadores de analizadores (ANTLR, Bison) o verificadores de modelos.
Lenguajes, gramáticas y máquinas
1. Alfabeto, palabra y lenguaje
Un alfabeto Σ es un conjunto finito de símbolos: {0, 1}, {A, B}, las letras del español o incluso un vocabulario de palabras. Una palabra es una secuencia finita de símbolos (ABBA); la palabra vacía se escribe ε. Un lenguaje es un conjunto de palabras, normalmente infinito: «todos los palíndromos sobre {A, B}».
Reconocer un patrón es decidir si una palabra pertenece a un lenguaje. Por eso, si describimos bien el lenguaje, ya sabemos qué tipo de máquina necesitamos.
2. Gramáticas
Una gramática genera las palabras de un lenguaje a partir de un símbolo inicial, aplicando reglas de sustitución. En una gramática libre de contexto cada regla sustituye un único no terminal sin mirar lo que lo rodea: S → A S A. Así se describen las estructuras anidadas: paréntesis, expresiones, bloques de código, frases.
Definición formal
G = (V, Σ, P, S): V son los no terminales, Σ los terminales, P las producciones A → α con A ∈ V y α ∈ (V ∪ Σ)*, y S ∈ V el símbolo inicial. L(G) = { w ∈ Σ* : S ⇒* w }.
El laboratorio usa el algoritmo de Earley (1970), que reconoce cualquier gramática libre de contexto en O(n³) —y en tiempo lineal en las gramáticas deterministas—, incluso con recursión por la izquierda y reglas ε.
3. La jerarquía de Chomsky
Cada nivel contiene al anterior. Subir de nivel significa dar más memoria a la máquina: de un número fijo de estados (autómata finito) a una pila (autómata de pila), a una cinta del tamaño de la entrada (autómata linealmente acotado) y a una cinta infinita (máquina de Turing).
Por qué un autómata finito no reconoce ABBA… (lema del bombeo)
Supongamos que un autómata con k estados reconociera los palíndromos. Al leer Aᵏ de la palabra AᵏBBAᵏ pasa por k+1 estados, así que repite alguno: hay un bucle que lee Aʲ (j ≥ 1). Repitiendo ese bucle aceptaría también Aᵏ⁺ʲBBAᵏ, que no es un palíndromo. Contradicción: hace falta memoria ilimitada, una pila.
4. La máquina de Turing
Alan Turing (1936) imaginó la máquina más sencilla capaz de hacer cualquier cálculo: una cinta infinita dividida en casillas, un cabezal que lee y escribe un símbolo y avanza o retrocede una casilla, y una tabla de estados que dice qué hacer en cada caso. Cuando llega a un estado de aceptación, da la entrada por buena.
Definición formal
M = (Q, Σ, Γ, δ, q₀, _, F): Q estados, Σ alfabeto de entrada, Γ ⊇ Σ alfabeto de cinta, _ ∈ Γ el blanco, δ: Q × Γ → Q × Γ × {L, R, S} la función de transición, q₀ el estado inicial y F ⊆ Q los estados de aceptación.
La tesis de Church-Turing afirma que todo lo que puede calcularse mediante un procedimiento mecánico lo calcula una máquina de Turing. Su ordenador, su móvil y cualquier lenguaje de programación tienen exactamente esa potencia (con memoria finita).
5. Lo que no tiene solución: el problema de la parada
¿Existe un programa que, dado cualquier otro programa y su entrada, diga si terminará? Turing demostró que no. El teorema de Rice lo generaliza: cualquier pregunta no trivial sobre lo que hace un programa arbitrario es indecidible.
La demostración en cuatro líneas
Supongamos que existe PARA(p, x), que responde siempre si el programa p termina con la entrada x. Construimos RARO(p): «si PARA(p, p), entra en un bucle infinito; si no, termina». ¿Qué hace RARO(RARO)? Si termina, es porque PARA dijo que no terminaba; si no termina, es porque PARA dijo que sí. Contradicción en ambos casos: PARA no puede existir.
En la práctica, eso no deja el problema sin salida: se restringe el tipo de programas, se ponen límites de pasos o de tiempo, o se aceptan análisis aproximados que a veces dicen «no lo sé». Pruebe la máquina «Bucle infinito» del simulador.
6. Reglas de transformación
Los algoritmos de Markov (1954) calculan solo con sustituciones de texto ordenadas: en cada paso se aplica la primera regla cuyo patrón aparece. Son tan potentes como una máquina de Turing y muestran que «computar» es, en el fondo, reescribir símbolos según reglas.
Acerca de Turing
Turing es una herramienta didáctica y gratuita para explorar los lenguajes formales y la computabilidad: diagnosticar qué tipo de máquina necesita un problema, simular máquinas de Turing, analizar gramáticas libres de contexto y aplicar reglas de transformación.
Todo se calcula en su navegador. Los diagnósticos son orientativos: clasificar correctamente un problema real depende de describirlo bien, y la pregunta general de si un problema arbitrario tiene solución es, como se explica en la teoría, indecidible.
Contacto
Privacidad y cookies
Esta herramienta funciona íntegramente en el navegador. No usa cookies, no tiene cuentas de usuario y no envía a ningún servidor los programas, gramáticas o textos que escriba.
El botón «Copiar enlace» guarda la máquina dentro de la propia dirección (después del símbolo #); esa parte de la dirección no se envía al servidor al abrirla, pero cualquiera con quien comparta el enlace podrá verla.
El alojamiento puede generar registros técnicos (dirección IP, fecha, recurso solicitado) para seguridad y mantenimiento.