Jerarquía de Chomsky

Noam 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

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, éste 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
0 recursivamente enumerable (LRE) Máquina de Turing (MT) Sin restricciones
1 dependiente del contexto (LSC) Autómata linealmente acotado αAβ → αγβ
2 independiente del contexto (LLC) Autómata con pila A → γ
3 regular (LR) Autómata finito AaB

Aa

Lenguajes Recursivamente Enumerables (de tipo 0)

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

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


\Rho = \{(u \rightarrow v) | u = xAy; u \in \Sigma^+; v,x,y \in \Sigma^*; A \in N\}

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

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:


\Rho = \{(S \rightarrow \lambda) o (xAy \rightarrow xvy) | v \in \Sigma^+; x, y \in \Sigma^*; A \in N\}

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

La mayoría de los lenguajes de programación entran en ésta 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:


\Rho = \{(S \rightarrow \lambda) o (A \rightarrow v) | v \in \Sigma^+; A \in N\}

Lenguajes Regulares (de tipo 3)

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:

\Rho = \{(S \rightarrow \lambda) o (A \rightarrow aB) o (A \rightarrow a) | a \in T; A, B \in N\}

Lineales por la izquierda:

\Rho = \{(S \rightarrow \lambda) o (A \rightarrow Ba) o (A \rightarrow a) | a \in T; A, B \in N\}

Véase también

Referencias

General

This article is issued from Wikipedia - version of the Monday, November 16, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.