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 1 es regular y L 2 no tiene contexto
(B) L 1 no tiene contexto pero no es regular y L 2 no tiene contexto
(C) Ni L 1 ni L 2 no tienen contexto
(D) L 1 libre de contexto pero L 2 no es libre de contexto
Respuesta: (A)
Explicación:
L1 = { wxyx ∣ w,x,y ∈ (0+1)+ }
En L 1 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 1 es lenguaje regular.
L2 = { xy ∣ x,y ∈ (a+b)*, ∣x∣=∣y∣, x≠y } is CFL
Observamos que una string está en L 2 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA