Jerarquia de Chomsky

Según Chomsky se clasifica las gramáticas en cuatro tipos (cuales son, como vemos más adelante, entre si verdaderamente diferentes).

Entonces sea $G=(\Sigma_N,\Sigma_T,P,\$)$ una gramática (y $\Sigma=\Sigma_N\cup\Sigma_T$). Las gramáticas se destinguen solamente en el sistema de producciones que siempre será un conjunto finito y que se clasifica en los siguientes tipos:

Tipo 0:

gramáticas generales sin restricciones

$$P\subset\mbox{$\Sigma^*$}.\Sigma_N.\mbox{$\Sigma^*$}\times\mbox{$\Sigma^*$}$$

es decir, se sustituye por lo menos un símbolo no-terminal.

Tipo 1:

gramáticas sensibles al contexto

$$P\subset\{xAy\longrightarrow xvy\;\vert\;x,y\in\mbox{$\Sigma^... ...\in\Sigma_N, v\in\Sigma^+\} \cup\{\$\longrightarrow \epsilon\}$$

es decir, se sustituye un símbolo no-terminal por algo manteniendo el contexto; entonces una derivación siempre produce palabras más largas o iguales ( $u\longrightarrow ^*v\Longrightarrow\vert u\vert\leq\vert v\vert$)

Tipo 2:

gramáticas libres de contexto

$$P\subset\Sigma_N\times\Sigma^+ \cup\{\$\longrightarrow \epsilon\}$$

es decir, se sustituye solo símbolos no-terminales por palabras no vacías

Tipo 3:

gramáticas regulares (o lineales)

$$P\subset\Sigma_N\times(\Sigma_N.\Sigma_T\cup\Sigma_T) \cup\{\$\longrightarrow \epsilon\}$$

es decir, lineales a la izquierda (porque los símbolos no-terminales aparecen en una derivación siempre a la izquierda de la palabra)

$$P\subset\Sigma_N\times(\Sigma_T.\Sigma_N\cup\Sigma_T) \cup\{\$\longrightarrow \epsilon\}$$

es decir, lineales a la derecha (porque los símbolos no-terminales aparecen en una derivación siempre a la derecha de la palabra)

• Se ha introducido explícitamente la regla $\$\longrightarrow \epsilon$ en las gramáticas de tipos 1, 2, y 3 para permitir que el lenguaje $\{\epsilon\}$ puede ser generado dado que las reglás solo permiten un crecimiento de la longitud de las palabras a lo largo de las derivaciones.
• Retomamos la clasificación de las gramáticas hacia final del curso (por ejemplo, respondemos a la pregunta si son de verdad clases separadas).

Observación: si permitimos para las gramáticas de libre contexto reglas del tipo $\Sigma_N\longrightarrow \mbox{$\Sigma^*$}$, es decir, permitimos reglas como $A\longrightarrow \epsilon$, podemos sustituir todas las reglas que tengan una $A$ a la derecha, por ejemplo $B\longrightarrow xAy$ por $B\longrightarrow xy$, y conseguir así una eliminación de las producciones compresoras.