Jerarquía De Chomsky

Introducción

Con este trabajo escrito, se pretende aprender a diferenciar cada una de estas gramáticas analizando sus estructuras. Como ya hemos aprendido con anterioridad, en esta materia, los lenguajes son conjuntos de palabras definidos por un alfabeto, los lenguajes que nos interesan dentro de esta materia tienen una estructura inherente. Las gramáticas nos marcan las reglas que hanconstruido el lenguaje. Para detectar esas reglas nos podemos hacer preguntas como estas: ¿Es nuestro lenguaje una sucesión de símbolos donde el siguiente depende del anterior o del siguiente? ¿Se puede separar cada palabra del lenguaje en partes más pequeñas que no dependan unas de otras? ¿Hay elementos que cambien su significado dependiendo del contexto? ¿No se ajusta a ninguna de estas premisas perose reconoce su estructura de alguna manera (mediante algún algoritmo) Cada lenguaje regular es a su vez libre del contexto, asimismo un lenguaje libre del contexto es también sensible al contexto, éste es recursivo y a su vez también es recursivamente numerable. Las inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes que no están en niveles anteriores.

MARCOTEORICO 1. Definición de la Jerarquía de Chomsky. Es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. En 1956 el lingüista norteamericano Noam Chomsky creó la Jerarquía de Chomsky para organizar los distintos tipos de lenguaje formal. En la cual cada lenguaje es descrito por el tipo de gramática generado. Estos lenguajes sirven como base para laclasificación de lenguajes de programación.

Los cuatro tipos de lenguajes son: lenguajes recursivamente enumerables, lenguajes sensibles al contexto, lenguajes libres de contexto y lenguajes regulares. Las cuatro clases de lenguajes suelen denominarse en forma conjunta jerarquía de Chomsky. A estos lenguajes también se les conocen como lenguajes del tipo 0, 1, 2 y 3.

Existe una exactacorrespondencia entre cada uno de estos tipos de lenguajes y particulares arquitecturas de máquinas en el sentido que por cada lenguaje de tipo T hay una arquitectura de máquina A que reconoce el lenguaje de tipo T y por cada arquitectura A hay un tipo T tal que todos los lenguajes reconocidos por A son de tipo T. La correspondencia entre lenguajes y arquitectura son mostrados en la siguiente tabla.Gramática Tipo – 0 Tipo – 1 Tipo – 2 Tipo- 3

Lenguaje Recursivamente enumerables Dependientes del contexto Independiente del contexto regular

Autómata Máquina de Turing Automatas linealmente acotados Autómatas a pila Autómata

Normas de producción Sin restricción αAβ → αγβ A→γ A → aB A→a

2. Jerarquía de Chomsky (tipos de gramáticas). Gramáticas de tipo 0 a) Definición formal. La gramáticade 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. La gramática de tipo 0 es una gramática estructurada sin ninguna restricción, o sea que sus reglas de producción tienen, en la parte izquierda al menos un símbolo no terminal y en la parte derecha cualquier secuencia determinales o no terminales, inclusive vacia. b) Características o propiedades. La gramática de Tipo 0 se aplica realmente a una en la que todas las producciones son de la forma α → β, donde α es una cadena de una o más variables. Las caracterizaciones de todos estos tipos de lenguajes en cuanto a las gramáticas hacen evidente que para 1 < i < 3, cada lenguaje de tipo i es de tipo i – 1, excepto que unlenguaje de contexto libre es sensible al contexto solo si no contiene la cadena nula. c) Ejemplos: G = (∑N, ∑T, P, S) ∑N = {S, U, V, X, Y, Z} ∑T = {a, b} P: S ZX Yb Zb X UV UVX VbX bY bZ λ bUZ │ aUY │ λ bV YX Ya Za aV Vb VaX aY aZ Va

El lenguaje generado por esta gramática es: L(G) = {ww / w ∈ ∑T }

Generación de algunas palabras S UVX X λ S UVX aUYX S UVX bUZX babaX baba

aUVaX aaX aa...