Aquí, w r es el reverso de la string w. ¿Cuáles de estos lenguajes son lenguajes libres de contexto deterministas?
(A) Ninguno de los lenguajes
(B) Solo L1
(C) Solo L1 y L2
(D) Los tres lenguajes
Respuesta: (C)
Explicación: Para L1 y L2 podemos diseñar autómatas de empuje hacia abajo deterministas, por lo que ambos son DCFL.
Pero para L3, no es posible diseñar PDA determinista, porque DPDA no puede determinar dónde termina exactamente ‘w’, por lo que podría comenzar a sacar símbolos (para w r ) de la pila.
Por lo tanto, la opción (C) 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