Open source project
This resource grows with the community. Explore the code, suggest improvements and share your ideas.
Computabilidad · Lenguajes formales
Explora pilas, autómatas finitos y la máquina de Turing con simuladores interactivos. Nada de teoría abstracta: toca, ejecuta y observa cómo funciona cada modelo.
El orden de llegada importa: pilas y colas estructuran datos.
Los autómatas deciden si una cadena pertenece a un lenguaje.
Turing define el límite de lo calculable.
Una ruta completa para entender cómo los modelos de computación leen, recuerdan, transforman y deciden sobre la información.
Alphabets, strings, languages and the minimum notation for precise explanations.
Start here 02 / MEMORYCompare LIFO, FIFO, finite states and auxiliary memory with runnable examples.
Open simulators 03 / METHODLearn to model a problem, follow a trace and prove that your idea works.
Use the method 04 / PRACTICEGraduated exercises, reasoned answers and a route for continued study.
Open exercisesAn alphabet Σ is a finite set of symbols. A string is a finite sequence of symbols; a language is a set of strings over Σ.
The central question is always: does w belong to L?
uv concatenates u and v; order matters.ε is the empty string and |ε| = 0.Σ* contains every finite string, including ε.Lᶜ contains the strings in Σ* that are not in L.L* allows concatenating zero or more strings from L.A model recognizes a language when it receives a string and answers yes/no. A generator describes how to produce valid strings. The same idea can be expressed as an automaton, a regular expression or a grammar.
Key idea: do not choose a model by the problem's name; choose it by the memory the solution needs.
Rule of thumb: a trace shows what happened for one input; an invariant explains why the model keeps working for every input.
Los mismos datos del simulador anterior, renderizados como bloques 3D. Arrastra para orbitar y usa la rueda para acercarte: cada push hace caer un bloque nuevo desde arriba.
Un autómata finito determinista lee una cadena símbolo a símbolo y salta entre estados según transiciones fijas. Si al terminar está en un estado de aceptación (doble círculo), la cadena pertenece al lenguaje.
L = cadenas binarias que terminan en «01» · q₂ es estado de aceptación (doble círculo)
—
Logros
Un AFD no puede recordar cuántas «a» leyó. Un autómata con pila añade una pila como memoria auxiliar, y de repente lenguajes como aⁿbⁿ se vuelven reconocibles: apila una ficha por cada «a» y desapila una por cada «b». Si la pila queda vacía justo al terminar, la cadena es válida.
L = aⁿbⁿ · aceptación: estado q₁ con pila vacía (solo el fondo Z)
La teoría deja de parecer una colección de dibujos cuando sigues siempre la misma secuencia: especificar, elegir memoria, ejecutar y demostrar.
Write the alphabet and a mathematical definition of L. Avoid ambiguous phrases such as “valid strings”.
If a finite summary is enough, use a DFA. If you must match or nest, think about a stack.
State the head position, current state and the symbols left to read or stored in memory.
Test ε, the shortest valid string, a near miss and a string that breaks the rule at the first symbol.
Explain what each state or memory symbol represents after every prefix has been read.
For w = 1101, the trace is:
q₀ —1→ q₀ —1→ q₀ —0→ q₁ —1→ q₂
It ends in q₂, so it accepts. The automaton only needs to remember the most relevant recent symbols.
After reading aⁱbʲ, the stack contains exactly Aⁱ⁻ʲ. If an a appears after a b, the language's shape has already been broken.
For aabb: push A, A; pop A, A; only Z₀ remains, so the string is accepted.
Confusing acceptance with halting: a TM may halt and reject; halting does not mean accepting.
Counting with a DFA: an arbitrary count cannot fit in finite memory.
Forgetting ε: the empty string may belong to the language and should be tested separately.
Drawing without an invariant: a nice diagram does not prove that it covers every string.
Induction: prove a base case and show that each step preserves the property.
Pumping lemma: use it to show that a language cannot be regular or context-free.
Closure: if a family is closed under union, complement or intersection, you can build new languages.
Reduction: transform a known problem into the one you are analyzing; if the first is impossible, so is the second.
More memory expands the class of languages you can recognize; it does not guarantee a fast algorithm.
Crea estados, conéctalos con transiciones 0/1, marca el inicial (doble clic) y los de aceptación. Tu autómata se guarda automáticamente y puedes exportarlo o importarlo como JSON.
clic para crear estados · arrastra para mover
doble clic sobre un estado → marcarlo como inicial · clic en la etiqueta de una transición (modo borrar) para eliminarla
Una cinta infinita, un cabezal que lee/escribe y un conjunto de reglas. Con solo eso, cualquier problema computable puede resolverse — y también quedan definidos los problemas indecidibles, como el problema de la parada.
Estado
q₀
Paso
0
Regla aplicada
—
Resultado
en espera
Esta máquina incrementa un número binario en 1. Recorre la cinta hasta el final y suma con acarreo hacia la izquierda.
La tesis de Church-Turing sostiene que nada que sea «computable» supera a esta máquina simple. Todo tu ordenador es, en esencia, una máquina de Turing muy rápida.
Cada tipo de gramática tiene su autómata asociado. A más potencia, más coste de cómputo.
| Tipo | Gramática | Autómata | Ejemplo de lenguaje |
|---|---|---|---|
| Type 3 | Regular | AFD / AFN | a*b | (ab)* |
| Type 2 | Context-free | Pushdown automaton | aⁿbⁿ |
| Type 1 | Context-sensitive | Linear bounded automaton | aⁿbⁿcⁿ |
| Type 0 | Unrestricted | Turing machine | todo lo decidible… y más |
El límite existe: hay problemas que ninguna máquina de Turing puede resolver — como decidir si un programa arbitrario termina (problema de la parada, Alan Turing, 1936). No es falta de velocidad ni memoria: es una imposibilidad matemática.
Las palabras que aparecen una y otra vez en teoría de la computación, explicadas en una línea para que puedas volver a ellas mientras resuelves.
Finite set of symbols allowed as input.
Every finite string over Σ, including the empty string ε.
A string with no symbols; its length is 0, but it is still a string.
Subset of Σ*. The recognition problem asks whether w ∈ L.
Rule that gives the next state or configuration after reading a symbol.
Summary of the information the model keeps at a given moment.
From a given configuration and symbol, there is at most one next action.
Property that remains true after every execution step.
A machine exists that always halts and answers yes or no correctly.
A machine accepts the language's strings, although it may not halt outside the language.
Property of a language family that remains in the family after an operation.
Transformation showing that solving one problem would let us solve another.
Intenta responder antes de abrir la solución. La explicación importa tanto como el resultado.
Yes. The string ends in 01 and the DFA trace ends in q₂. Its length and earlier symbols do not change that condition.
No. It has two a symbols and three b symbols. The PDA runs out of stack tokens before reading the last b; the counts must match.
Use two states: q_even (initial and accepting) and q_odd. On 0, stay in the same state; on 1, switch between them.
A remains above the bottom marker Z₀: three tokens were pushed and two were popped. The string is not accepted yet because one b is missing.
1000. The machine changes each 1 to 0 while carrying left; when it reaches the blank, it writes a 1.
In a correctly implemented stack, all three operations are O(1). Traversing or copying the entire stack costs O(n).
Once this page feels familiar, compare your solutions with reference texts: Introduction to the Theory of Computation by Michael Sipser, Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani and Ullman, or An Introduction to Formal Languages and Automata by Peter Linz.
Community tip: share the trace and reasoning, not only the final answer.
Tres desafíos que cruzan todo lo aprendido. Tu progreso se guarda y completarlos todos desbloquea logros.
Escribe una cadena de longitud ≥ 5 que termine en q₂ (es decir, que sea aceptada).
¿Qué número produce la máquina al incrementar 1011? Escribe el resultado en binario.
Escribe una cadena aceptada por el autómata con pila con exactamente n a seguidas de n b, donde n ≥ 2.