PUERTA | PUERTA CS 2019 | Pregunta 40

¿Cuál de los siguientes idiomas sobre ∑ = {a, b} NO está libre de contexto?
(A) {a ^{n segundo yo} ⏐ yo ∈ {n, 3n, 5n}, n≥ 0}
(B) {wa ⁿ w ^R segundo norte ⏐ w ∈ {a, b ^} *, n≥ 0}
(C) {ww ^R ⏐ w ∈ {a, b}*}
(D) {wa ⁿ b ⁿ w ^R ⏐ w ∈ {a, b}*, n≥ 0}

Respuesta: (B)
Explicación: (A): Es CFL, porque tenemos una unión de tres CFL, y las CFL están cerradas bajo propiedad de la unión .

{anbi ⏐ i ∈ {n, 3n, 5n}, n≥ 0} 
= anbn ∪ anb3n ∪ anb5n 

Podemos identificar strings de este lenguaje usando solo una pila.

(B): No es CFL, porque puede identificar strings de un idioma dado usando solo una pila, necesita al menos 2 pilas. Existe una coincidencia de string alternativa que no es posible usando solo una pila. Es un lenguaje sensible al contexto pero no libre de contenido.

(C): Es una LFC muy conocida. Es un lenguaje de palíndromo sobre solo dos alfabetos que se pueden reconocer usando solo una pila.

(D): También es CFL, ya que primero podemos pulsar w, luego a, b pop con a y wR pop con w. Entonces PDA puede aceptar el idioma.

La opción (B) es correcta.

Cuestionario de esta pregunta