¿Son todos los lenguajes libres de contexto y regulares eficientemente decidibles?

12

Encontré esta figura que muestra que los lenguajes libres de contexto y regulares son subconjuntos (adecuados) de problemas eficientes (supuestamente ). Entiendo perfectamente que los problemas eficientes son un subconjunto de todos los problemas decidibles porque podemos resolverlos, pero podría llevar mucho tiempo.P

¿Por qué todos los lenguajes libres de contexto y regulares son eficientemente decidibles? ¿Significa que resolverlos no llevará mucho tiempo (quiero decir que lo sabemos sin más contexto)?

ingrese la descripción de la imagen aquí

formal-languages regular-languages context-free efficiency Gigili
fuente
3
Por curiosidad, ¿dónde encontraste esta figura? Puede ser útil tener un contexto para explicar, ya que "eficiente" no es una noción formal y diferentes personas pueden usarlo para significar cosas diferentes.
Gilles 'SO- deja de ser malvado'
2
Si "eficiente" significa " " (como es común), "eficiente" no significa "no mucho tiempo" ya que los polinomios también producen valores enormes. Tenga en cuenta que un resultado básico en la complejidad es que hay infinitas secuencias de problemas, cada una más fácil que la siguiente. Esto se mantiene dentro y fuera de . P∈PP
Raphael
@Raphael: En este contexto, eficiente es una clase de lenguajes que son decidibles en tiempo polinómico. Utilicé "podría tomar mucho tiempo" para problemas decidibles en lugar de indecidibles para los que no podemos encontrar soluciones en un tiempo finito.
Gigili
la forma técnica correcta de decir esto es que determinar si w∈L donde w es una palabra y L es un idioma está en P. ie / aka "reconocimiento de idioma"
vzn

Respuestas:

15

La membresía regular del idioma se puede decidir en tiempo simulando el DFA (mínimo) del idioma (que se ha calculado previamente).O(n)

La membresía de un lenguaje libre de contexto se puede decidir en mediante el Algoritmo CYK .O(n3)

Hay idiomas decidibles que no están en , como los de .E X P T I M E ∖ PPEXPTIME∖P

Dave Clarke
fuente
2
Es posible que desee mencionar el algoritmo de multiplicación de matrices para gramáticas sin contexto que tiene un mejor tiempo de ejecución, y que este algoritmo funciona de manera muy eficiente (linealmente) en casi cualquier gramática práctica sin contexto: sciencedirect.com/science/article/pii / 030439759190180A
Alex ten Brink
@AlextenBrink No creo que esta pregunta pida una granularidad más fina que "polinomio o no".
Raphael
1
Tenga en cuenta que no necesita el autómata mínimo, siempre que sea determinista. El tiempo de ejecución seguirá siendo , ya que en cada paso hay un posible "próximo movimiento" único. O(n)
Janoma
1
De hecho, para los idiomas normales, ni siquiera necesita explícitamente autómatas deterministas. Simula todos los cálculos en paralelo al realizar un seguimiento de todos los estados de esa manera imitando la construcción del conjunto de potencia.
Hendrik
1
@Dave: lineal en la longitud de la cadena de entrada, para un lenguaje regular fijo, como las otras complejidades dadas aquí.
Hendrik
1

Refinamiento / "letra pequeña" en la respuesta de DC: todas las CFL en forma de Chomsky Normal Form se pueden analizar de manera eficiente con el algoritmo CYK y todas las CFL se pueden convertir a CNF. Sin embargo, la conversión de un CFL arbitrario a CNF puede tomar espacio exponencial en el peor de los casos, dependiendo de algunos algoritmos. (No conozco un algoritmo que garantice la conversión del tiempo P aquí, ¿hay alguien más? Uno debe considerar todos los casos extremos / peores, como CFL no deterministas o ambiguos ). Wikipedia dice en la sección CNF Orden de transformaciones

Además, la mayor hinchazón en el tamaño de la gramática [nota 4] depende del orden de transformación. Usando | G | para denotar el tamaño de la gramática original G, el aumento de tamaño en el peor de los casos puede variar de a , dependiendo del algoritmo de transformación utilizado. [6]: 72 2 | G ||G|222|G|

Por lo tanto, parece que pueden existir CFL que no se pueden analizar de manera eficiente. La mayoría de los lenguajes de programación se pueden transmitir de manera eficiente a CNF (o tal vez se definen principalmente en CNF o casi CNF), por lo tanto, el análisis de CFL para lenguajes "típicos" es "prácticamente" en P. Probablemente haya alguna investigación moderna sobre la peor complejidad del caso (pero no encontrar documentos recientes sobre la búsqueda superficial). Por ejemplo, este trabajo de investigación más antiguo (1973) de Greibach también parece indicar que el rendimiento en el peor de los casos puede no estar limitado por P. ver, por ejemplo.

vzn
fuente