PUERTA | PUERTA-CS-2000 | Pregunta 5

Sea L el lenguaje generado por la gramática S -> 0S0/00. ¿Cual de los siguientes es verdadero?
(A) L = 0+
(B) L es regular pero no 0+
(C) L es libre de contexto pero no regular
(D) L no es libre de contexto

Respuesta: (B)
Explicación : L no es 0+ porque 0+ contendrá cualquier string arbitraria sobre el alfabeto 0 con cualquier número de 0 (excepto string vacía), por ejemplo: {0, 00, 000,00000}, pero L solo tendrá strings como { 00, 0000, 000000,… }, es decir, solo un número par de 0 (excluyendo la string vacía}.

: L es un lenguaje libre de contexto , porque la gramática G que genera el lenguaje L es una gramática libre de contexto. Una Gramática G es CFG si todas sus producciones son de la forma A->α, donde A es un solo no terminal y α pertenece a (V∪ T)*, es decir, α puede ser una string de terminales y/o No -terminales. (V representa un no terminal y T representa un terminal)

: L es un lenguaje regular , porque podemos escribir una expresión regular para él (y también podemos hacer un autómata finito), que es (00)+.

: Por lo tanto, esta opción es correcta, porque, como demostramos anteriormente.
Cuestionario de esta pregunta