PUERTA | PUERTA-CS-2004 | Pregunta 87

El lenguaje {a ^m b ⁿ C ^m+n | m, n ≥ 1} es

(A) regular
(B) libre de contexto pero no regular
(C) sensible al contexto pero no libre de contexto
(D) tipo 0 pero no sensible al contexto

Respuesta: (B)
Explicación:
Construimos un PDA para el lenguaje dado.

PUSH Z ₀ en la pila inicialmente.
PUSH X en la pila para cada aparición de ‘a’.
PUSH Y en la pila para cada ocurrencia de ‘b’.
POP X e Y de la pila para cada ocurrencia de ‘c’.

Si después de extraer todos los X e Y de la pila, no queda ningún elemento de entrada en la string y obtenemos Z ₀ en la parte superior de la pila, entonces se acepta la string.

 
Por lo tanto, la opción (B) es correcta.

 
Comente a continuación si encuentra algo incorrecto en la publicación anterior.

Cuestionario de esta pregunta