Jerarquización de gramáticas

Las gramáticas pueden ser de distintos tipos, de acuerdo con las características que rigen la formulación de reglas de producción válidas, todos los cuales parten de las gramáticas arbitrarias que son aquellas que consideran la existencia infinita de cadenas formadas por los símbolos del lenguaje. Los principales tipos derivados son:

– Gramáticas sensibles al contexto. Este tipo de gramáticas tiene la característica de que el lado derecho de la regla de producción siempre debe ser igual o mayor que el lado izquierdo.

– Gramáticas independientes del contexto. Es aquella que cumple con las propiedades de la gramática sensible al contexto y que, además, tiene la característica de que el lado izquierdo de la regla de producción sólo debe tener un elemento y éste no puede ser un elemento terminal.

– Gramáticas regulares. Es aquella que cumple con las características de la gramática independiente del contexto y, además, se restringe a través de las reglas de producción para generar sólo reglas de los dos tipos anteriores.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM