PUERTA | PUERTA CS 2021 | Juego 2 | Pregunta 51

Para una string w, definimos w ^R como el reverso de w. Por ejemplo, si w = 01101 entonces w ^R = 10110.

¿Cuál de los siguientes lenguajes es/son libres de contexto?
(A) {wxw ^R x ^R ∣ w,x∈{0,1}*}
(B) {ww ^R xx ^R ∣ w,x∈{0,1}*}
(C) {wxw ^R ∣ w,x ∈{0,1}*}
(D) {wxx ^R w ^R ∣ w,x∈{0,1}*}

Respuesta: (B) (C) (D)
Explicación: Opción A: L={wxw^R x^R | w, x ∈ {0,1}* }
Esto no es CFL, ya que si presionamos «w» y luego «x», entonces no podemos hacer coincidir w^R con «w» ya que la parte superior de la pila contiene x.

Opción B: L={ww^R xx^R | w, x ∈ {0,1}* }
Esto es CFL. No adivinamos de manera determinista el medio de la string. Así que presionamos «w», luego hacemos coincidir con w^R y nuevamente presionamos x y hacemos coincidir con x^R

Opción C: L={wxx^R w^R | w, x ∈ {0,1}* }
Esto también es CFL. No adivinamos de manera determinista el medio de la string. Entonces presionamos «w», luego presionamos x y luego emparejamos con x^R y nuevamente emparejamos con w^R

Opción D: L={ancho x ancho^R | w, x ∈ {0,1}* }
Este es un lenguaje regular (por lo tanto, CFL). En este idioma, cada string comienza y termina con el mismo símbolo (ya que x puede expandirse).
Cuestionario de esta pregunta