Jerarquía de Chomsky

Jerarquía de Chomsky
Noam Chomsky.

En lingüística la jerarquía de Chomsky 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.

Contenido

La jerarquía

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 \alpha A\beta \rightarrow \alpha\gamma\beta con A un no terminal y α, β y γ cadenas de terminales y no terminales. Las cadenas α y β pueden ser vacías, pero γ no puede serlo. La regla S \rightarrow \epsilon está permitida si S 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 2 (gramáticas libres del contexto) generan los lenguajes independientes del contexto. Las reglas son de la forma A \rightarrow \gamma con A un no terminal y γ una cadena de terminales y no terminales. Estos lenguajes son aquellos que pueden ser reconocidos por un autómata con pila.
  • 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 S \rightarrow \epsilon también está permitida si S 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, é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 (RL) Autómata finito A → aB

A → a

Lenguajes Recursivamente Enumerables (de tipo 0)

Artículo principal: Lenguaje recursivamente enumerable

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, 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)

Artículo principal: lenguaje regular

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

  • Joaquín Aranda, Natividad Duro, José Luis Fernández, José Jiménez, Fermando Morilla, "Fundamentos de Lógica Matemática y Computación", Sanz y Torres, 2006, ISBN 84-96094-74-X.

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Jerarquía de Chomsky — En lingüística la jerarquía de Chomsky 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 …   Enciclopedia Universal

  • Noam Chomsky — durante una visita en Vancouver, Canadá, en 2004 Nombre …   Wikipedia Español

  • Noam Chomsky — Avram Noam Chomsky (7 de diciembre de 1928) es profesor de lingüística en el MIT (Instituto de Tecnología de Massachusetts). Se le atribuye la creación de la teoría de la gramática generativa, considerada con frecuencia la principal contribución… …   Enciclopedia Universal

  • Gramática formal — Esta imagen muestra la relación entre las cadenas de caracteres, las fórmulas bien formadas y los teoremas. En algunos sistemas formales, sin embargo, el conjunto de los teoremas coincide con el de las fórmulas bien formadas. Una gramática formal …   Wikipedia Español

  • Gramática generativa transformacional — Gramática transformacional es una expresión que designa al tipo de gramática generativa que utiliza reglas transformacionales u otros mecanismos para representar el desplazamiento de constituyentes y otros fenómenos del lenguaje natural. En… …   Wikipedia Español

  • Gramática — Antonio de Nebrija impartiendo gramática en presencia del mecenas Juan de Zúñiga. Miniatura de las Introductiones latinae, 1481. La Gramática es el estudio de las reglas y principios que regulan el uso de las lenguas y la organización de las… …   Wikipedia Español

  • Lenguaje formal — Esta imagen muestra la relación entre las cadenas de caracteres, las fórmulas bien formadas y los teoremas. En algunos sistemas formales, sin embargo, el conjunto de los teoremas coincide con el de las fórmulas bien formadas. En matemáticas,… …   Wikipedia Español

  • Gramática (autómata) — Una gramática ( G ) desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman… …   Wikipedia Español

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • Máquina de Turing — Para otros usos de este término, véase Turing (desambiguación). Una máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”