Glosario

Los términos principales del curso, ordenados por parte.

Lenguajes regulares

Término English Definición
Alfabeto alphabet Conjunto finito y no vacío de símbolos. Se escribe Σ.
Cadena string Secuencia finita de símbolos de un alfabeto.
Cadena vacía empty string La cadena de longitud 0. Se escribe ε.
Lenguaje language Un conjunto de cadenas sobre un alfabeto. Puede ser infinito.
Problema de decisión decision problem Problema cuya respuesta es sí o no. Equivale a un lenguaje: las entradas con respuesta sí.
Autómata finito determinista (DFA) deterministic finite automaton Máquina con un número fijo de estados que lee la cadena una vez, símbolo por símbolo, y con cada símbolo pasa a un único estado.
Estado de aceptación accept state Estado en el que, si la máquina termina de leer ahí, acepta la cadena.
Función de transición transition function La regla δ que dice a qué estado se pasa desde cada estado con cada símbolo.
Función de transición extendida extended transition function δ*: el estado al que llega el autómata desde un estado después de leer una cadena entera. En un NFA, el conjunto de estados.
Lenguaje regular regular language Lenguaje que algún DFA reconoce.
Construcción del producto product construction DFA cuyos estados son pares de estados de otros dos, y que los simula a la vez. Da la unión y la intersección.
Autómata finito no determinista (NFA) nondeterministic finite automaton Autómata que desde un estado puede tener varias transiciones con el mismo símbolo, o ninguna. Acepta si algún camino acepta.
Transición ε ε-transition Transición que el NFA puede tomar sin leer ningún símbolo.
Clausura ε ε-closure Los estados a los que se llega desde un conjunto de estados usando solo transiciones ε.
Construcción de subconjuntos subset construction Convierte un NFA en un DFA cuyos estados son conjuntos de estados del NFA.
Propiedades de cierre closure properties Operaciones que, aplicadas a lenguajes de una clase, dan un lenguaje de la misma clase.
Expresión regular regular expression Descripción de un lenguaje con símbolos, unión, concatenación y estrella.
Estrella de Kleene Kleene star A* es el conjunto de todas las concatenaciones de cero o más cadenas de A.
Teorema de Kleene Kleene’s theorem Un lenguaje es regular si y solo si alguna expresión regular lo describe.
Lema de bombeo pumping lemma Toda cadena larga de un lenguaje regular tiene un tramo que se puede repetir sin salir del lenguaje. Sirve para demostrar que un lenguaje no es regular.
Cadenas distinguibles distinguishable strings Dos cadenas x, y para las que existe un sufijo z tal que solo una de xz, yz está en el lenguaje.
Teorema de Myhill-Nerode Myhill-Nerode theorem Un lenguaje es regular si y solo si tiene un número finito de clases de cadenas indistinguibles, y ese número es el de estados de su DFA mínimo.
DFA mínimo minimal DFA El DFA con menos estados que reconoce un lenguaje. Es único salvo los nombres de los estados.
Streaming streaming Modelo en el que los datos se leen una sola vez, con mucha menos memoria que el tamaño de la entrada.

Lenguajes libres de contexto

Término English Definición
Gramática libre de contexto (CFG) context-free grammar Reglas que reemplazan una variable por una cadena de variables y terminales, sin mirar lo que la rodea.
Variable variable Símbolo de la gramática que todavía se puede reemplazar.
Terminal terminal Símbolo del alfabeto del lenguaje: ya no se reemplaza.
Derivación derivation Secuencia de reemplazos que lleva de la variable inicial a una cadena de terminales.
Derivación por la izquierda leftmost derivation Derivación que en cada paso reemplaza la variable que está más a la izquierda.
Árbol de derivación parse tree Árbol que muestra qué regla se aplicó a cada variable, sin importar el orden.
Gramática ambigua ambiguous grammar Gramática en la que alguna cadena tiene dos árboles de derivación distintos.
Lenguaje libre de contexto context-free language Lenguaje que alguna gramática libre de contexto genera.
Forma normal de Chomsky Chomsky normal form Gramática en la que toda regla es A → BC o A → a, donde B y C no son la variable inicial. Solo la inicial puede tener la regla S → ε. Toda gramática se puede llevar a esta forma.
CYK CYK Algoritmo de programación dinámica que decide en O(n³) si una gramática en forma normal de Chomsky genera una cadena.
Autómata de pila (PDA) pushdown automaton NFA con una pila de memoria sin límite. Reconoce exactamente los lenguajes libres de contexto.
Pila stack La memoria del PDA: solo se lee, se saca o se pone el símbolo de arriba.
Parser parser Programa que, dada una cadena, construye su árbol de derivación o informa que no lo tiene.

Computabilidad

Término English Definición
Máquina de Turing Turing machine Autómata con una cinta infinita que puede leer y escribir, y un cabezal que se mueve en los dos sentidos.
Cinta tape La memoria de la máquina de Turing: celdas infinitas hacia la derecha. Al empezar tiene la entrada y, después, blancos.
Cabezal head Señala la celda de la cinta que la máquina lee y escribe. Se mueve una celda por paso.
Símbolo blanco blank symbol El símbolo de las celdas que no tienen entrada. Se escribe ⊔, y _ en los archivos del curso.
Configuración configuration El estado, el contenido de la cinta y la posición del cabezal en un instante.
Tesis de Church-Turing Church-Turing thesis Todo lo que se puede calcular con un procedimiento mecánico se puede calcular con una máquina de Turing. No es un teorema.
Decidir decide Una máquina decide un lenguaje si con toda entrada se detiene, y acepta exactamente las cadenas del lenguaje.
Reconocer recognize Una máquina reconoce un lenguaje si acepta exactamente sus cadenas. Con las demás puede rechazar o no detenerse.
Decidible decidable Lenguaje que alguna máquina de Turing decide.
Reconocible recognizable Lenguaje que alguna máquina de Turing reconoce.
Decididor decider Máquina de Turing que se detiene con toda entrada. Decide el lenguaje de las cadenas que acepta.
Reconocedor recognizer Máquina de Turing que acepta exactamente las cadenas de un lenguaje. Con las demás puede rechazar o no detenerse.
Correconocible co-recognizable Lenguaje cuyo complemento es reconocible. Un lenguaje es decidible si y solo si es reconocible y correconocible.
Enumerador enumerator Máquina de Turing con una impresora: imprime, en algún orden, las cadenas de un lenguaje. Un lenguaje es reconocible si y solo si algún enumerador lo enumera.
Función computable computable function Función que alguna máquina de Turing calcula: se detiene con toda entrada w y deja f(w) en la cinta.
Codificación encoding Representación de un objeto (una máquina, un grafo) como cadena. Se escribe ⟨M⟩.
Máquina universal universal Turing machine Máquina que recibe ⟨M, w⟩ y simula a M con la entrada w.
Diagonalización diagonalization Técnica que construye un objeto distinto de cada uno de una lista, cambiando el elemento i en la posición i.
Numerable countable Conjunto finito, o que se puede poner en correspondencia con los números naturales. Las máquinas de Turing son numerables; los lenguajes, no.
Problema de la parada halting problem Decidir si una máquina se detiene con una entrada. Es indecidible.
Reducción reduction Convertir las instancias de un problema A en instancias de otro B, de modo que resolver B resuelva A.
Reducción por función mapping reduction Reducción dada por una función computable f tal que w ∈ A si y solo si f(w) ∈ B.
Propiedad no trivial nontrivial property Propiedad del lenguaje de una máquina que alguna máquina tiene y alguna no.
Teorema de Rice Rice’s theorem Toda propiedad no trivial del lenguaje que reconoce una máquina es indecidible.
Historia de cómputo computation history La secuencia de configuraciones de una máquina con una entrada, desde la inicial hasta una final.
Problema de correspondencia de Post (PCP) Post correspondence problem Dadas fichas con una cadena arriba y otra abajo, decidir si alguna secuencia de fichas da la misma cadena arriba y abajo. Es indecidible.
Teorema de recursión recursion theorem Toda máquina se puede escribir de modo que tenga acceso a su propia descripción.
Quine quine Programa que imprime su propio código fuente sin leerlo de ningún archivo.
Teoremas de incompletitud incompleteness theorems En todo sistema formal razonable que exprese la aritmética hay afirmaciones verdaderas que no se pueden demostrar en él.
Complejidad de Kolmogorov Kolmogorov complexity La longitud de la descripción más corta de una cadena. No se puede calcular.
Cadena incompresible incompressible string Cadena x con K(x) ≥ |x|: ninguna descripción es más corta que ella misma.

Complejidad

Término English Definición
Complejidad en tiempo time complexity El número máximo de pasos de una máquina con entradas de longitud n.
P P Lenguajes que una máquina de Turing determinista decide en tiempo polinomial.
Verificador verifier Algoritmo que recibe una entrada y un certificado, y comprueba que la entrada está en el lenguaje.
Certificado certificate La información extra que un verificador usa: una solución propuesta.
Fórmula booleana Boolean formula Expresión con variables, ∧, ∨ y ¬. Una asignación le da a cada variable el valor verdadero o falso.
Cláusula clause Disyunción de literales. Una fórmula en CNF es una conjunción de cláusulas.
NP NP Lenguajes con verificador en tiempo polinomial. Equivale a: decididos por una máquina no determinista en tiempo polinomial.
Reducción en tiempo polinomial polynomial-time reduction Reducción por función que se calcula en tiempo polinomial.
NP-completo NP-complete Problema de NP al que se reduce todo problema de NP.
Teorema de Cook-Levin Cook-Levin theorem SAT es NP-completo.
Tableau tableau Tabla con una configuración de la máquina por fila. Es la pieza central de la demostración de Cook-Levin.
Ventana window Bloque de 2 × 3 celdas del tableau. Es legal si puede aparecer en un cómputo de la máquina.
NP-difícil NP-hard Problema al que se reduce en tiempo polinomial todo problema de NP. Si además está en NP, es NP-completo.
coNP coNP Lenguajes cuyo complemento está en NP.
Complejidad en espacio space complexity El número máximo de celdas de la cinta que una máquina usa con entradas de longitud n.
PSPACE PSPACE Lenguajes decididos con espacio polinomial.
PSPACE-completo PSPACE-complete Lenguaje de PSPACE al que se reduce en tiempo polinomial todo lenguaje de PSPACE. TQBF lo es.
Teorema de Savitch Savitch’s theorem Lo que una máquina no determinista hace con espacio f(n), una determinista lo hace con espacio f(n)².
TQBF TQBF Decidir si una fórmula booleana con todos sus cuantificadores es verdadera. Es PSPACE-completo.
Fórmula booleana cuantificada quantified Boolean formula Fórmula booleana a la que se le antepone ∃ o ∀ para sus variables. El orden de los cuantificadores importa.
Geografía generalizada generalized geography Juego sobre un grafo dirigido en el que dos jugadores alternan movimientos sin repetir nodos. Decidir quién gana es PSPACE-completo.
Estrategia ganadora winning strategy Regla que le dice a un jugador qué elegir en cada posición para ganar, juegue lo que juegue el otro.
L y NL L, NL Lenguajes decididos con espacio logarítmico, de forma determinista y no determinista.
NL-completo NL-complete Lenguaje de NL al que se reduce en espacio logarítmico todo lenguaje de NL. PATH lo es.
Teoremas de jerarquía hierarchy theorems Con más tiempo, o con más espacio, se pueden decidir estrictamente más lenguajes.
Función construible constructible function Función f que una máquina puede calcular a partir de 1ⁿ con espacio O(f(n)) (construible en espacio) o en tiempo O(f(n)) (construible en tiempo).
Oráculo oracle Caja que responde en un paso si una cadena está en un lenguaje fijo.
Relativización relativization Una demostración relativiza si sigue valiendo cuando todas las máquinas tienen el mismo oráculo. Ninguna demostración que relativice resuelve P frente a NP.
BPP BPP Lenguajes decididos en tiempo polinomial por un algoritmo que usa azar y se equivoca con probabilidad a lo sumo 1/3.
Amplificación amplification Repetir un algoritmo probabilístico y tomar la respuesta mayoritaria, para bajar el error tanto como se quiera.