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.

La Jerarquía de Chomsky consta de cuatro niveles:

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.

${displaystyle A ightarrow { ext{a}}B}$

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

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

${displaystyle mathrm {P} ={(u ightarrow v)|u=xAy;uin Sigma ^{+};v,x,yin Sigma ^{*};Ain N}}$

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:

${displaystyle mathrm {P} ={(S ightarrow lambda )o(xAy ightarrow xvy)|vin Sigma ^{+};x,yin Sigma ^{*};Ain N}}$

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:

${displaystyle mathrm {P} ={(S ightarrow lambda )o(A ightarrow v)|vin Sigma ^{+};Ain N}}$

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:

${displaystyle mathrm {P} ={(S ightarrow lambda )o(A ightarrow aB)o(A ightarrow a)|ain T;A,Bin N}}$

Lineales por la izquierda:

${displaystyle mathrm {P} ={(S ightarrow lambda )o(A ightarrow Ba)o(A ightarrow a)|ain T;A,Bin N}}$