En función de la forma de sus producciones, se puede caracterizar qué tan compleja es una gramática formal. Noam Chomsky mostró que esta caracterización clasifica jerárquicamente a las gramáticas formales: Gramáticas en un nivel están incluidas en los siguientes niveles y la inclusión entre niveles es propia.
Se puede dar varios refinamientos de la Jerarquía de Chomsky. En la tabla (4) presentamos esquemáticamente uno de tales refinamientos.
Table 4:
Jerarquía gramatical de Chomsky.
Tipo
Nombres
Forma de producciones
0
Irrestricta
1
Irrestricta con memoria limitada
existe una función (computable) tal que la longitud de cualquier cadena en una derivación que dé una palabra
ha de estar acotada por el valor de la función en la longitud de
,
2
Sensibles al contexto con borro
3
Sensibles al contexto no reductivas
,
,
4
Libres de contexto
5
Libres de contexto deterministas
producciones libres de contexto con la particularidad de que una vez que se ha derivado prefijos de un cierto tamaño entonces se tendrá determinada la palabra a derivarse,
6
Lineales
7
Regulares
la tipología empleada denota lo siguiente:
negritas
cadenas de caracteres;
A
alfabeto, ,
MAYÚSCULAS
símbolos variables;
T
conjunto de símbolos terminales,
V
conjunto de símbolos variables.
Lo esquemático de esta tabla se suprimirá en el capítulo 3 de este curso, en el que se presentará estas gramáticas con todo detalle.
En toda gramática formal aparecen dos problemas fundamentales:
Problema de la palabra:
Instancia:
Solución:
Es decir, este problema consiste en decidir, para una gramática y una palabra dadas, si acaso la palabra está generada por la gramática.
Problema de la derivación:
Instancia:
Solución:
Es decir, este problema consiste en encontrar, cuando exista, una derivación, en una gramática dada, de una palabra dada también.
Los problemas mencionados pueden ser resueltos efectivamente en algunos niveles de la Jerarquía de Chomsky. En otros niveles superiores puede ser irresolubles estos problemas.
Siguiente:AutómatasUn nivel arriba:Introducción a la teoría Anterior:Una formalización de gramáticasGuillermo Morales-Luna
2000-06-27