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.

Noam Chomsky.

La jerarquía

editar

La Jerarquía de Chomsky consta de cuatro niveles:

  • Gramáticas de tipo 0 (sin restricciones), que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuya decisión puede ser realizada por una máquina de Turing que se detenga.
  • Gramáticas de tipo 1 (gramáticas sensibles al contexto) generan los lenguajes sensibles al contexto. Estas gramáticas tienen reglas de la forma   con   un no terminal y  ,   y   cadenas de terminales y no terminales. Las cadenas   y   pueden ser vacías, pero   no puede serlo. La regla   está permitida si   no aparece en la parte derecha de ninguna regla. Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados.
  • Gramáticas de tipo 3 (gramáticas regulares) generan los lenguajes regulares. Estas gramáticas se restringen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal. La regla   también está permitida si   no aparece en la parte derecha de ninguna regla. Estos lenguajes son aquellos que pueden ser aceptados por un autómata finito. También esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares.

Nótese que el conjunto de gramáticas correspondiente a los lenguajes recursivos no es un miembro de la jerarquía.

Cada lenguaje regular es a su vez libre del contexto, asimismo un lenguaje libre del contexto es también dependiente del contexto, este es recursivo y a su vez, recursivamente enumerable. Las inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes que no están en niveles anteriores.

Tipo Lenguaje Autómata Normas de producción de gramáticas Ejemplos
0 recursivamente enumerable (LRE) Máquina de Turing     describe una máquina de Turing 
1 dependiente del contexto (LSC) Autómata linealmente acotado    
2 independiente del contexto (LLC) Autómata con pila    
3 regular (LR) Autómata finito   

 

 
Significado de los símbolos:
  •   = terminal
  •  ,   = no terminal
  •  ,  ,   = cadena de terminales y/o no terminales
  •  ,  ,   = cadena posiblemente vacía
  •   = cadena no vacía


Lenguajes Recursivamente Enumerables (de tipo 0)

editar

Las gramáticas que generan estos lenguajes pueden tener reglas compresoras.

Las reglas de producción son de la siguiente forma:


 

Lenguajes Dependientes del Contexto (sensibles al contexto, de tipo 1)

editar

No existen reglas compresoras en toda la teoría, salvo, opcionalmente, la que deriva el axioma a la palabra vacía.

Existen reglas en las que un símbolo no terminal puede derivar a formas sentenciales distintas, según los símbolos que aparezcan a su alrededor.

Las reglas de producción son de la siguiente forma:


 

Lenguajes Independientes del Contexto (Libres de contexto, De tipo 2)

editar

La mayoría de los lenguajes de programación entran en esta categoría en cuanto su forma sintáctica, aunque en realidad los lenguajes de programación son dependientes del contexto, se reconocen a través de lenguajes de tipo 2 porque su reconocimiento es de O(n) mientras que los de tipo 1 tienen un orden de reconocimiento O(n^3) en el peor caso. Por este motivo se ejecuta un análisis semántico para reconocer si el programa es correcto.

Las reglas de producción son de la siguiente manera:


 

Lenguajes Regulares (de tipo 3)

editar

Son los lenguajes más simples dentro la Jerarquía de Chomsky. Se suelen expresar mediante expresiones regulares.

Existen 2 tipos: lineales por la derecha y lineales por la izquierda. Las reglas de producción son de la siguiente forma:

Lineales por la derecha:

 

Lineales por la izquierda:

 

Véase también

editar

Referencias

editar

General

editar