Siguiente: Autómatas Un nivel arriba: Introducción a la teoría Anterior: Una formalización de gramáticas

Jerarquía de Chomsky

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	$\mbox{\bf p} \rightarrow \mbox{\bf q},\ \ \mbox{\bf p} \in A^+,\mbox{\bf q} \in A^*$
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 $\mbox{\bf x}$ ha de estar acotada por el valor de la función en la longitud de $\mbox{\bf x}$,
2	Sensibles al contexto con borro	$\mbox{\bf p} B \mbox{\bf r} \rightarrow \mbox{\bf p}\mbox{\bf q}\mbox{\bf r},\ \ \mbox{\bf q} \in A^*$
3	Sensibles al contexto no reductivas	$S \rightarrow \mbox{\it nil\/}$, $\mbox{\bf p} B \mbox{\bf r} \rightarrow \mbox{\bf p}\mbox{\bf q}\mbox{\bf r},\ \ \mbox{\bf q} \in A^+$,
4	Libres de contexto	$B \rightarrow \mbox{\bf q},\ \ \mbox{\bf q} \in A^*$
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	$B \rightarrow \mbox{\bf p}U\mbox{\bf r},\ \ \mbox{\bf p},\mbox{\bf r} \in T^*$
7	Regulares	$B \rightarrow \mbox{\bf p}U,\ \ \mbox{\bf p} \in A^*$

la tipología empleada denota lo siguiente:

negritas	cadenas de caracteres;	A	alfabeto, $A=T\cup V$,
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ómatas Un nivel arriba: Introducción a la teoría Anterior: Una formalización de gramáticas