Problema de vacío

En la informática teórica y la teoría del lenguaje formal , un lenguaje formal es vacío si su conjunto de oraciones válidas es el conjunto vacío . El problema de la vacuidad es la cuestión de determinar si un lenguaje es vacío dada alguna representación del mismo, como un autómata de estados finitos . ^{[ 1 ]} Para un autómata que tiene${\displaystyle n}$estados, este es un problema de decisión que se puede resolver en${\displaystyle O(n^{2})}$tiempo , ^{[ 2 ]} o en tiempo${\displaystyle O(n+m)}$si el autómata tiene n estados y m transiciones. Sin embargo, variantes de esa pregunta, como el problema de vacuidad para autómatas de pila sin borrado , son PSPACE-completas . ^{[ 3 ]} El problema de vacuidad en el aprendizaje automático y los lenguajes formales determina si un modelo o autómata genera el lenguaje vacío , que es indecidible para ciertos autómatas finitos multicabeza alternantes sobre alfabetos de una sola letra. ^{[ 4 ]}

El problema de la vacuidad es indecidible para las gramáticas sensibles al contexto , un hecho que se deduce de la indecidibilidad del problema de la parada . Sin embargo, es decidible para las gramáticas libres de contexto . ^{[ 3 ]}

• Problema de no vacuidad en intersecciones