PUERTA | PUERTA 2017 MOCK II | Pregunta 41

El lenguaje L = {WbcW ^R | W ∈ (a+b)*} es _____.
(A) DCFL
(B) CFL pero no DCFL
(C) No-CFL
(D) Ninguna de las anteriores

Respuesta: (A)
Explicación: Cualquier idioma para el que podamos tener un PDA determinista es siempre un DCFL.
Aquí para lenguaje L= {WbcWR | W ∈ (a+b)*} podemos tener una PDA con las siguientes transiciones en las que la PDA acepta una string cuando se detiene en un estado final. q0 en estado inicial y qf es estado final.

1. (q0, a, Z) -> (q0, aZ)

2. (q0, b, Z) -> (q0, bZ)

3. (q0, a, a) ->(q0, aa)

4. (q0, b, a) -> (q0, ba)

5. (q0, a, b) -> (q0, ab)

6. (q0, b , b) -> (q0, bb)

7. (q0, c, b) -> (q1, nulo)

8. (q1, a, a) ->(q1, nulo)

9. (q1, b, b) -> (q1, nulo)

10. (q1, nulo, Z ) -> (qf, Z)

Aquí todos los a y b se colocan inicialmente en la pila para W. Tan pronto como ocurre ac después de b , B se extrae de la pila después de lo cual se comprueba W^R. Si los alfabetos de string adicionales coinciden con el
alfabeto de la pila, el alfabeto se extrae de la pila y, finalmente, la string alcanza el estado final si el idioma tiene la forma L= {WbcW^R | W ∈ (a+b)*}.

Por lo tanto, el lenguaje anterior es un DCFL.

Cuestionario de esta pregunta