Introducción

En 1956 y 1959, el lingüista norteamericano Noam Chomsky publicó dos trabajos sobre los Lenguajes Naturales que, aplicados al área de los Lenguajes Formales, produjeron lo que se conoce como Jerarquía de Chomsky.

Establece una clasificación (según las restricciones que se imponen a sus producciones) de cuatro tipos de gramáticas formales que, a su vez, generan cuatro tipos diferentes de lenguajes formales.

Jerarquía de Chomsky

Esta jerarquía establece una clasificación jerárquica de los diferentes tipos de gramáticas y lenguajes, organizándolas en cuatro niveles diferentes: Tipo 0, Tipo 1, Tipo 2 y Tipo 3. Cada tipo se caracteriza por un conjunto específico de reglas de producción y propiedades.

A lo largo de la materia vamos a ir viendo los distintos tipos comenzando desde el núcleo y yendo hacia afuera.

  1. Tipo 0: Lenguajes/Gramáticas irrestrictas o Lenguajes/gramáticas generales. O también lenguajes recursivamente numerables. Las gramáticas de Tipo 0 son las más generales y menos restringidas. Las palabras de este lenguaje son generadas por gramáticas irrestrictas. No imponen ninguna restricción sobre las reglas de producción. Pueden generar lenguajes que incluyen todos los lenguajes formales posibles. Las reglas de producción pueden ser de cualquier forma y no hay restricciones en las transformaciones que se pueden realizar. Estas gramáticas son difíciles de analizar y tienen aplicaciones en el estudio de la teoría de la computación y la formalización de la semántica.
  2. Tipo 1: Lenguajes/Gramáticas sensibles al contexto. Las gramáticas de Tipo 1, también conocidas como gramáticas sensibles al contexto. Son aquellos lenguajes cuyas palabras son generadas por las gramáticas dependientes del contexto. Esta gramática tienen reglas de producción en las que el lado izquierdo es una cadena de símbolos y el lado derecho contiene una cadena de símbolos que es al menos tan larga como el lado izquierdo. Estas gramáticas se utilizan para describir lenguajes que se pueden reconocer por una máquina de Turing no determinista con una cinta ilimitada. Se aplican en el análisis de lenguajes naturales y en el diseño de compiladores.
  3. Tipo 2: Lenguajes/Gramáticas independientes del contexto. Las gramáticas de Tipo 2, conocidas como gramáticas independientes del contexto. Son aquellos lenguajes que sus palabras son generadas por las gramáticas independientes del contexto. Estas gramáticas tienen reglas de producción en las que el lado izquierdo es un solo símbolo no terminal y el lado derecho puede ser cualquier cadena de símbolos, incluyendo tanto terminales como no terminales. Estas gramáticas son utilizadas para describir lenguajes formales que se pueden analizar sintácticamente mediante un autómata de pila. Son ampliamente utilizadas en la especificación de lenguajes de programación y en la construcción de analizadores sintácticos.
  4. Tipo 3: Lenguajes/gramáticas regulares. Las gramáticas de Tipo 3, también conocidas como gramáticas regulares, son las más restringidas de la jerarquía. Los lenguajes regulares son aquellos que sus palabras son formados por un sistema formal, una especie de mecanismo, llamado gramáticas regulares. Estas gramáticas tienen reglas de producción en las que el lado izquierdo es un solo símbolo no terminal y el lado derecho puede ser un solo terminal o un terminal seguido de un solo símbolo no terminal. Los lenguajes regulares son aquellos que pueden ser reconocidos por autómatas finitos deterministas o no deterministas. Estos lenguajes se utilizan comúnmente en la descripción de patrones en expresiones regulares y en la implementación de analizadores léxicos.

Untitled

Untitled

Mientras más nos acerquemos al núcleo, mayor serán las restricciones. Por el contrario, mientras más al exterior vayamos, más poderosos serán los lenguajes.

Gramáticas

Las 4 gramáticas están formadas por 4 elementos, por eso se dicen que son una cuádrupla: G = (ΣT, ΣN, S, P) donde:

Autómatas

Los autómatas son máquinas abstractas de estados que reconocen si una palabra pertenece o no a un lenguaje dado. Si la palabra es aceptada, el autómata la reconoce; si no, la rechaza.