haskell - resueltos - Correspondencia entre clases de tipo y niveles de gramática en la jerarquía de Chomsky

jerarquia de chomsky ejercicios resueltos

Question

Mi pregunta es sobre las clases de tipo Aplicativo y Mónada por un lado, y los niveles de gramática libres de contexto y sensibles al contexto de la jerarquía de Chomsky por el otro.

He escuchado que hay una correspondencia entre las clases de tipos y los niveles de gramática. ¿Qué tan exacta es esta correspondencia?

Es decir, ¿pueden analizarse todas las gramáticas libres de contexto sin utilizar métodos más fuertes que los combinadores aplicativos, y todas las gramáticas pueden analizarse utilizando nada más fuerte que los combinadores aplicativos libres de contexto? En otras palabras, ¿la clase de tipo Applicative corresponde exactamente a las gramáticas libres de contexto?

Y la misma pregunta, excepto con ''libre de contexto'' sustituido por ''sensible al contexto'' y Applicative by Monad.

Aclaración de recompensas: ¿Las clases de tipo corresponden a los niveles de gramática? Por ejemplo, ¿hay un conjunto de clases de tipos que proporcionen todas las operaciones necesarias para los lenguajes regulares de expresión y nada más?

La motivación para la pregunta es que estaba trabajando en un analizador, y quería determinar en qué nivel de gramática estaba mi implementación en función de los combinadores que usé. es posible?

Answer 1

No creo que nadie lo haya mostrado formalmente. La razón es que ni el aplicativo ni la mónada pueden analizar gran parte de nada por sí mismos. Más bien, también necesitas

1. Elección (MonadPlus, Alternativa)
2. Recursion

Dicho esto, con la opción (no determinista) y la recursión (arbitraria), los analizadores aplicativos esencialmente coinciden exactamente con la interfaz para el BNF (y por lo tanto pueden analizar todas las CFL), mientras que las mónadas pueden proporcionar operaciones sensibles al contexto arbitrarias.