Si las strings de un idioma L pueden enumerarse efectivamente en orden lexicográfico (es decir, alfabético), ¿cuál de las siguientes afirmaciones es verdadera?
(A) L es necesariamente finito
(B) L es regular pero no necesariamente finito
(C) L es independiente del contexto pero no necesariamente regular
(D) L es recursivo pero no necesariamente independiente del contexto
Respuesta: (D)
Explicación:
Las strings de un el idioma L se puede enumerar de manera efectiva significa que existe una máquina de Turing para el idioma L que enumerará todas las strings válidas del idioma.
Si la string está en orden lexicográfico, TM aceptará la string y se detendrá en el estado final.
Pero, si la string no está en orden lexicográfico, TM rechazará la string y se detendrá en un estado no final.
Por lo tanto, L es un lenguaje recursivo.
No podemos construir PDA para el lenguaje L. Entonces, el lenguaje dado no está libre de contexto.
Por lo tanto, la opción (D) es correcta.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA