En la ciencia informática teórica y la teoría del lenguaje formal , un lenguaje formal está vacío si su conjunto de oraciones válidas es el conjunto vacío . El problema del vacío es la cuestión de determinar si un lenguaje está vacío dada alguna representación del mismo, como un autómata de estados finitos . [1] Para un autómata que tiene estados, este es un problema de decisión que se puede resolver en el tiempo , [2] o en el tiempo si el autómata tiene n estados y m transiciones. Sin embargo, las variantes de esa cuestión, como el problema del vacío para autómatas de pila que no se borran , son PSPACE-completos . [3]
El problema del vacío es indecidible para gramáticas sensibles al contexto , un hecho que se desprende de la indecidibilidad del problema de la detención . Sin embargo, es decidible para gramáticas independientes del contexto . [3]
