Page 39 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

39

CLASIFICACIÓN DE LOS LENGUAJES FORMALES – JERARQUÍA DE CHOMSKY

En lingüística la jerarquía de Chomsky (ocasionalmente también llamada la Jerarquía de
Chomsky–Schützenberger) es una clasificación jerárquica de distintos tipos de gramáticas
formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en
1956.

Chomsky clasificó jerárquicamente los lenguajes en una jerarquía inclusiva de cuatro grados o
niveles; y es inclusiva porque cada grado contiene a todos los siguientes. Las gramáticas formales
que generan lenguajes formales, que a su vez se asocian a diferentes tipos de autómatas.

Importante notar que a cada lenguaje existe una definición de autómata que lo resuelve.

Clasificación de Chomsky:

TIPO 0

TIPO 1

TIPO 2

TIPO 3

Tipo 0: es el más general, es al que pertenecen la semántica de los lenguajes naturales y
artificiales. Estos lenguajes no tienen restricción alguna. El conjunto de las gramáticas del tipo 0,
se relaciona con los problemas computables o recursivamente numerables (los que se resuelven a
través de la máquina de Turing.

Tipo 1: corresponden a los lenguajes sensibles al contexto. En este tipo, se introducen algunas
limitaciones en la estructura gramatical, pero se permite que el valor sintáctico de las palabras
dependa de su posición en la frase, es decir de su contexto. Todas las gramáticas del tipo 1 pueden
analizarse mediante autómatas lineales acotados.

Tipo 2: corresponden a los lenguajes independientes del contexto. Aquí se restringe aún más la
libertad de la formación de reglas gramaticales, o sea el valor sintáctico de una palabra es
totalmente independiente de su posición en la frase. Todos los lenguajes, sin excepción, se puede
decir que se pueden expresar mediante gramáticas del tipo 2 de Chomsky.

Tipo 3: corresponden a un tipo de lenguaje muy sencillo, llamados lenguajes regulares, se
construyen con restricciones muy estrechas. La gramática de cualquier lenguaje regular se puede
analizar mediante un autómata finito. Estas máquinas abstractas se aplican en el análisis y diseño
orientado a objeto, para la determinación y especificación de los cambios de estado de los objetos
que pertenecen a una clase determinada.