PUERTA | PUERTA-CS-2005 | Pregunta 57

Considere los idiomas:

L1 = {wwR |w ∈ {0, 1}*}
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww |  w ∈  (0, 1}*)

¿Cuál de las siguientes es VERDADERA?
(A) L1 es una CFL determinista
(B) L2 es una CFL determinista
(C) L3 es una CFL, pero no una CFL determinista
(D) L3 es una CFL determinista

Respuesta: (B)
Explicación:  

L1: {sw^R | w pertenece a {0,1}*}
Esta es una CFL pero no una DCFL. Se puede derivar de la siguiente gramática
S -> aSa | bSb | epsilon
Pero no se puede derivar de ningún autómata pushdown determinista, porque no hay forma de averiguar dónde termina una palabra y comienza su reverso.

L2: {w#w^R | w pertenece {0,1}*}
Esta es una CFL, por la misma razón descrita anteriormente. Este es un CFL determinista porque tenemos un marcador que nos ayuda a encontrar el final de la palabra w y el comienzo de su reverso. Por lo tanto, un PDA en el que se empujan todos los alfabetos hasta obtener # y luego aparece solo si la parte superior de la pila coincide con el alfabeto actual y se rechaza en caso contrario, derivará L2.

L3: {sw | w pertenece a {0,1}*}
Esto ni siquiera es una CFL. La afirmación anterior podría probarse usando el lema de bombeo:
considere una string z de la forma (0 ^ n 1 ^ n 0 ^ n 1 ^ n).
Suponiendo que L3 es una CFL y que z obviamente satisface L3, por lo tanto, z también debería satisfacer el lema de bombeo.
Tomaremos n tal que n = p, donde p es la longitud de bombeo de L3, por lo que nuestra string debe tener una longitud mayor que la longitud de bombeo.
Ahora, según el lema de bombeo, debe existir u,v,w,x,y tal que z = uvwxy, |vwx| <= p, |vx| > 0 y u{v^i}x{y^i}z pertenece a L3 para todo i>=0.
No existe tal configuración de u,v,w,x,y tal que u{v^0}x{y^0}z pertenezca a L3. Por lo tanto, z no satisface el lema de bombeo. Por lo tanto, L3 no es una CFL.

Teniendo en cuenta todas las conclusiones anteriores, la única opción correcta es (B) L2 es una CFL determinista.

Referencia ;

https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec17.pdf

Esta solución es aportada por .
Cuestionario de esta pregunta