Jerarquía de Chomsky

Demos un breve repaso a la jerarquía de gramáticas de Chomsky:

Tipo 0: Contiene reglas que transforman un número arbitrario de símbolos no vacío en otro número arbitrario, posiblemente vacío, de símbolos.

aAB -> a

bB -> aBC

Tipo 1: Una gramática es tipo 1 monotónica si no contiene reglas donde el lado izquierdo consista en más símbolos que el lado derecho:

|A| <= |B| A ->B

AF -> ABab
S -> aAB

Una gramática es tipo 1 sensible al contexto si todas sus reglas son sensibles al contexto. Una regla es sensible al contexto si solo un símbolo no terminal en el lado izquierdo se reemplaza por otro símbolo mientras el resto permanece inalterado y en el mismo orden.

bQc -> bbcc

o la gramática que genera el mismo número de a, b, c:

Ss -> abc | aSQ

bQc -> bbcc

cQ -> Qc

Tipo 2: Son gramáticas libres de contexto cuando en su lado izquierdo siempre aparece un único no-terminal

A -> a|b|c

B -> A|CaA

C -> A,C|A

Tipo 3: Son gramáticas regulares o de estados finitos cuando en su lado derecho sóilo se contiene un no-terminal y además se encuentra al final de la producción. Esto produce dos clases de reglas:

- Un no-terminal produce cero o más terminales
- Un no-terminal produce cero o más terminales seguidos por un no-terminal.

La definición original de Chomsky lo restringe:

- Un no-terminal produce un terminal
- Un no-terminal produce un terminal seguido por un no-terminal


Por ejemplo (no-terminales empiezan en mayúsculas):

Sentence -> tom|dick|harry|List

List -> tom List Tail | dick List Tail | harry List Tail

List Tail -> ,List | and tom | and dick | and harry

El siguiente tipo no pertenece a la jerarquía oficial propuesta por Chomsky:

Tipo 4: Gramáticas de elección finita (FC), no se permite ningún no-terminal a la derecha y el símbolo inicial de la gramática tiene una lista finita de alternativas.

Un ejemplo de por qué es más restrictiva una gramática regular que una independiente del contexto viene dado por la siguiente situación equivalente al problema de determinar que en una expresión (o en un trozo de código programado) el número de elementos que abren (por ejemplo paréntesis o llaves) es igual al número de elementos que cierran:

Sea ∑ el alfabeto ∑={a,b} y L la gramática independiente del contexto (GIC) siguiente L={b, aba, aabaa, aaabaaa,...} = {aⁿbaⁿ, n≥0}

Lo más parecido con una expresión regular sería L_r={a^*ba^*}, dónde * no asegura coincidencia.

Conclusión: Las expresiones regulares no saben contar, con lo que podemos apreciar que tenemos una gramática más restrictiva que la anterior.

Recordemos que una gramática es tanto más restrictiva cuanto mayor es el orden de su tipo. Por lo tanto, las gramáticas más restrictivas son las regulares, lo que significa que pueden modelar un número menor de comportamientos del lenguaje, como el presentado de su incapacidad para contar.

El lenguaje natural, el utilizado por el ser humano, se podría considerar dentro de una gramática tipo 0, lo que nos permite generar un número infinito de construcciones lingüísticas correctas, incluso de manera creativa o inventiva.

El problema en el caso del Procesamiento del Lenguaje Natural está servido, cuanto menos restrictiva es una gramática, mayor dificultad para su implementación automática.

En el caso de los analizadores léxicos suele ser suficiente la implementación de una gramática tipo 3, y en el caso de los lenguajes de programación, incluso con una semántica pronunciada, se pueden implementar con una gramática tipo 2.

¿Qué pasa pues con el lenguaje natural? Pues aunque en su infinitud pertenezcan a los tipo 0, la mayoría de aplicaciones de PLN pueden ser implementadas mediante gramáticas de tipo 1, incluso apurando, en aplicaciones concretas, de tipo 2.

Pero en cualquier caso este tipo de gramáticas sigue siendo de difícil implementación sobre todo cuando su tamaño y crecimiento hacen necesario el manejo de grandes árboles conceptuales, por lo que aplicaciones actuales, como el traductor automático Google Translator, hacen uso de técnicas estadísticas, obteniendo resultados similares a otros traductores clasistas como Systran, así como otras muchas aplicaciones de recuperación de información hacen uso intenso de reconocimiento de entidades, n-gramas, expresiones regulares (gramáticas tipo 4) para y combinadas con lo anterior, hibridaciones entre gramática/estadística (o métodos de aprendizaje automático...)

Siendo simple en nuestros pensamientos, ¿por qué tenemos que imitar el funcionamiento del cerebro humano con una única y compleja teoría si podemos hacerlo mezclando millones de ellas de lo más simples? Quién sabe cuándo se nos dará una respuesta... por el momento, aquí queda un breve resumen de la jerarquía del padre de la gramática generativa transformacional.