Jerarquía de Chomsky

Jerarquía de Chomsky

Ingeniería en Sistemas

​Lenguaje

​Un lenguaje definido sobre un alfabeto, es un conjunto de palabras construidas con los símbolos de ese alfabeto.

​Teoría de la Computación

​El estudio de la Teoría de Computación comienza por los lenguajes ya que son éstos los que permiten describir y formular problemas.

​

Puede definirse el lenguaje como el conjunto de signos (o palabras) y de reglas que los organizan. El signo es, a su vez, un concepto abstracto que permite hacer referencia a objetos. El proceso por el cual se toma un objeto como signo de algo se llama interpretación; y la interpretación determina que el signo actúe como tal, ya sea porque permite relacionar al signo con su objeto o bien porque el signo se asocia a una idea o pensamiento.

​Símbolos, alfabetos y palabras

​Las computadoras actuales y todos los dispositivos digitales, solo almacenan dos señales diferentes: cero - uno, prendido - apagado, sí - no.

​Con solo dos señales y una adecuada codificación puede representarse cualquier conjunto de símbolos, tales como:

• ​letras de algún alfabeto humano

• ​caracteres especiales de control

• ​dígitos y símbolos especiales

​Símbolos, alfabetos y palabras

​Se denomina alfabeto a cualquier conjunto finito y no vacío de símbolos.

​En este contexto, los símbolos de un alfabeto suelen llamarse también letras o caracteres:

​

​Una palabra definida sobre un alfabeto es cualquier secuencia finita de símbolos de dicho alfabeto, escritos a continuación uno del otro. Las palabras a su vez pueden concatenarse entre ellas para formar nuevas palabras:

​

​Noam Abraham Chomsky

• ​Lingüista, filósofo, politólogo y activista estadounidense de origen judío.

• ​Desarrolló trabajos en teoría lingüística y ciencia cognitiva.

• ​Propuso la gramática generativa, disciplina que situó la sintaxis en el centro de la investigación lingüística.

• ​Chomsky ha concentrado su interés en la elaboración de una gramática general y universal, que trata de formular una serie de reglas capaces de generar o producir todas las oraciones posibles y aceptables de una lengua.

Gramática Generativa

• ​Con este paradigma, cambiaron la perspectiva, los programas y métodos de investigación en el estudio del lenguaje.

• ​La gramática generativa se refiere al conjunto de marcos teóricos para el estudio de la sintaxis de las lenguas.

• ​Esta proporciona un conjunto de reglas o principios que predicen correctamente las combinaciones que aparecen en oraciones gramaticalmente correctas para una determinada lengua (sintaxis).

• ​Concibe a la lengua como una estructura.

Gramática Generativa

Gramática Generativa Transformacional

• ​Como tal, una gramática transformacional es una expresión usada para designar al tipo de gramática generativa que utiliza reglas transformacionales para representar el desplazamiento de constituyentes y otros fenómenos del lenguaje natural.

• ​Reglas como Concordancia de Número o Concordancia de Género y Persona.

​Gramáticas Formales

​Por tanto, en 1956, Noam Chomsky al presentar su Teoría de las Gramáticas Transformacionales-Generativas, puede decirse que "aritmetizó" la lengua, en el mismo sentido que George Boole lo había hecho cien años antes con la lógica.

​

​Chomsky propuso una nueva forma de estudiar lenguajes usando símbolos y notaciones al estilo matemático, usado los sistemas de producción, construyendo un álgebra para el tratamiento de los lenguajes.

​Gramáticas Formales

Y aún así, la teoría de Chomsky se basaba por completo en lenguajes naturales.

​Fue gracias a John Backus y Peter Naur, diseñadores de lenguajes de computadora, que las ideas de Noam Chomsky fueron adaptadas y utilizadas en las ciencias computacionales, puesto que en la misma época ellos desarrollaban losp rimeros lenguajes de programación de alto nivel: Fortran y Algol.

​Gramáticas Formales

Una gramática formal G es una cuádrupla, en la cual sus cuatro componentes representan:

• ​El alfabeto de símbolos que formarán las cadenas del lenguaje que se está describiendo y es denominado alfabeto de símbolos terminales.

• ​Un conjunto de variables o símbolos auxiliares llamado alfabeto de símbolos no terminales.

• ​Un símbolo no terminal distinguido denominado axioma o símbolo inicial.

• ​Un conjunto de producciones de la forma A := B, donde ambas palabras están compuestas de símbolos terminales y símbolos no terminales.

​Lenguajes Formales

¿En qué forma describe la gramática formal un lenguaje? y ¿Cómo se determina que una palabra pertenece o no al lenguaje descripto?

​Dada una gramática formal, se llama lenguaje formal generado por G al conjunto de todas las cadenas de símbolos terminales que puedan derivarse desde el axioma S utilizando las reglas de producción de P.

​Jerarquía de Chomsky

​Se han llamado Lenguajes Formales, a aquellos que pueden ser generados por gramáticas formales.

​En su trabajo, Chomsky estableció que todos los lenguajes formales podían clasificarse en cuatro tipos, denominados

• lenguajes tipo 0: Lenguajes estructurados por frases o recursivamente enumerables

• lenguajes tipo 1: Lenguajes dependientes del contexto

• lenguajes tipo 2: Lenguajes independientes del contexto

• lenguajes tipo 3: Lenguajes regulares o lineales

​

Estos solo se distinguen por el formato de las producciones de las gramáticas que los generan.

​

​Mientras más restricciones se le ponen a las producciones, menos lenguajes pueden describir, por lo que su clasificación es inclusiva.

​Jerarquía de Chomsky

​Tipo 0: Lenguajes estructurados por frases

​También llamados lenguajes recursivamente enumerables, son los más generales en la jerarquía y están descriptos por las reglas de reescritura menos restrictivas, por lo que a veces también se dice que son lenguajes irrestrictos.

​

​El autómata que puede reconocer este tipo de lenguajes, en general, es llamado Máquina de Turing.

​Tipo 1: Lenguajes dependientes del contexto

​O sensibles al contexto, son lenguajes que permiten el reemplazo contextual de símbolos no terminales.

​

​

​Esto nos dice que el símbolo no terminal A, solo puede ser reemplazado por la cadena E de terminales y no terminales si se encuentra flanqueada por alfa a la izquierda y por beta a la derecha, es decir, en el contexto alfa-beta.

​El autómata que generalmente reconocen este tipo de lenguajes es el autómata linealmente acotado.

​Tipo 2: Lenguajes independientes del contexto

​O de contexto libre, son los lenguajes sobre los que más esfuerzo e investigación se ha efectuado a la fecha, ya que la sintaxis de la gran mayoría de los lenguajes de programación de computadoras se describe con gramáticas independientes del contexto.

​

​

​El autómata que puede reconocer este tipo de lenguajes es el autómata con pila.

​Tipo 3: Lenguajes regulares

​Los elementos de los que se compone un lenguaje de programación (identificadores, constantes, palabras clave, etc.) conforman lenguajes regulares y pueden ser especificados utilizando gramáticas regulares y expresiones regulares.

​Estas describen en forma sencilla importante cantidad de patrones por lo que se las utiliza ampliamente en herramientas de desarrollo de sistemas y para, por ejemplo, las operaciones de administración de los sistemas operativos.

​

​El autómata que puede reconocer este tipo de lenguajes es el autómata finito.

​Actividad

​Obtener todas las derivaciones posibles de las siguientes gramáticas y determinar el tipo de lenguaje generado en cada caso (puede interpretar más de uno):

​

a) G1 = ({c,d}, {D,E}, D, P1)

​ P1 = {D := cE | d, E := cd}

​b) G2 = ({0,1}, {S,A,B}, S, P)

​ P2 = {S := 0B | 0A1, A := 0B | 0, B := 1}