Algoritmos de decisión de lenguages libres de contexto

Pertenencia:

¿$w\in L$? sí, se puede contestar la pregunta (es decir, es un problema computable) porque

• construimos un autómata que acepte $L$ (por ejemplo en estado final)
• simulamos su comportamiento leyendo la palabra $w$
• si acabamos en un estado final, $w$ está en $L$, sino $w$ no está en $L$

dicha simulación puede tener tiempo de cálculo exponential, otra posibilidad es

• construimos una gramática en forma normal de Chomsky
• aplicamos el algoritmo de Cocke-Younger-Kasami que resuelve el problema en tiempo de orden $O(n^3)$.

Vaciedad:

¿$L=\emptyset$? sí, se puede contestar la pregunta (es decir, es un problema computable) porque

• construimos una gramática que genere $L$
• analizamos si el símbolo inicial es útil, si es útil, entonces $L$ no es vacío, sino $L$ es vacío

Cardinalidad:

¿$\vert L\vert<\infty$? sí, se puede contestar la pregunta (es decir, es un problema computable) porque

• construimos una gramática que genere $L$ en su forma normal de Chomsky
• analizamos el grafo de posisibles sustituciones de símbolos para averigüar si existe un ciclo
• si existe tal ciclo, entonces $L$ es infinito, sino $L$ es finito

Igualidad:

¿$L_1=L_2$? no, no se puede contestar la pregunta (es decir, es un problema no computable).

• antes de entender dicha respuesta negativa, hay que estudiar más a fondo la teoría de las Máquinas de Turing.