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. |