Sean Nf y Np las clases de lenguajes aceptados por autómatas finitos no deterministas y autómatas push-down no deterministas, respectivamente. Sean Df y Dp las clases de lenguajes aceptados por los autómatas finitos deterministas y los autómatas push-down deterministas, respectivamente. ¿Cuál de las siguientes es VERDADERA?
(A) Df ⊂ Nf y Dp ⊂ Np
(B) Df ⊂ Nf y Dp = Np
(C) Df = Nf y Dp = Np
(D) Df = Nf y Dp ⊂ Np
Respuesta: (D)
Explicación: autómatas pushdown deterministas puede reconocer todos los lenguajes deterministas libres de contexto, mientras que los no deterministas pueden reconocer todos los lenguajes libres de contexto. Principalmente los primeros se utilizan en el diseño de analizadores (Fuente:http://en.wikipedia.org/wiki/Pushdown_automaton ). Los lenguajes libres de contexto deterministas (DCFL) son un subconjunto adecuado de lenguajes libres de contexto.
Los autómatas finitos no deterministas y los autómatas finitos deterministas aceptan el mismo conjunto de lenguajes, ya que los NFA se pueden traducir a DFA equivalentes mediante el algoritmo de construcción de subconjuntos.
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