PUERTA | PUERTA CS 2020 | Pregunta 42

Considere los siguientes idiomas.

L1 = { wxyx ∣ w,x,y ∈ (0+1)+ }
L2 = { xy ∣ x,y ∈ (a+b)*, ∣x∣=∣y∣, x≠y } 

¿Cuál de las siguientes es VERDADERA?
(A) L ₁ es regular y L ₂ no tiene contexto
(B) L ₁ no tiene contexto pero no es regular y L ₂ no tiene contexto
(C) Ni L ₁ ni L ₂ no tienen contexto
(D) L ₁ libre de contexto pero L ₂ no es libre de contexto

Respuesta: (A)
Explicación:

L1 = { wxyx ∣ w,x,y ∈ (0+1)+ } 

En L ₁ poniendo x como 0 y 1 obtenemos un subconjunto,

L1 = w0y 0 + w1y1 
L1 = (0 + 1)+0(0 + 1)+0 + (0 + 1)+1(0 + 1)+1 

Entonces, L ₁ es lenguaje regular.

L2 = { xy ∣ x,y ∈ (a+b)*, ∣x∣=∣y∣, x≠y } is CFL

Observamos que una string está en L ₂ si y solo si puede escribirse como xy con |x| = |y| tal que para algún i, el i-ésimo carácter de x es diferente del i-ésimo carácter de y. Para obtener una string de este tipo, comenzamos a generar los i-ésimos caracteres correspondientes y completamos los caracteres restantes.

Con base en la idea anterior, definimos el CFG para C de la siguiente manera:

S → AB | BA
A → XAX | 0
B → XBX | 1
X → 0 | 1 

La opción (A) es correcta.

Cuestionario de esta pregunta