1. (a) Cierto, dado que todo lenguaje regular está libre de contexto, todo lenguaje libre de contexto es decidible, y todo lenguaje decidible es reconocible por Turing.
¿Por qué los lenguajes independientes del contexto son decidibles?
Un problema indecidible no tiene un algoritmo que determine la respuesta para una entrada dada Ambigüedad de los lenguajes libres de contexto: Dado un lenguaje libre de contexto, no hay una máquina de Turing que siempre se detiene en un tiempo finito y responde si el lenguaje es ambiguo o no.
¿Es decidible el subconjunto de un lenguaje independiente del contexto?
2 Respuestas. Σ es independiente del contexto (de hecho, es regular) y tiene muchos subconjuntos. Si L es un lenguaje libre de contexto de tamaño infinito, entonces hay subconjuntos J de L que son decidibles y algunos que son indecidibles. Por ejemplo, el subconjunto vacío es decidible.
¿Son decidibles las LFC?
CFL: es decidible para el problema del vacío, el problema de la finitud y el problema de pertenencia.
¿Cuántos idiomas son independientes del contexto?
(1) Hay un número contablemente infinito de idiomas libres de contexto. Esto es cierto porque cada descripción de un lenguaje libre de contexto tiene una longitud finita, por lo que hay un número infinito numerable de tales descripciones. (2) Hay un número incontable de idiomas.
