PUERTA | Cuestionario para Sudo GATE 2021 | Pregunta 45 – Part 1

El lenguaje L = {WbcW ^R | W ∈ (a+b)*} es _____.

Nota: esta pregunta es de selección múltiple (MSQ).
(A) Regular
(B) DCFL
(C) CFL
(D) CFL pero no DCFL

Respuesta: (B) (C)
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, entonces CFL.
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior