Compiladores

/ TRABAJO COOPERATIVO / PERIODO I[pic 2][pic 3][pic 4]

Jerarquía de Chomsky

En 1956 Noam Chomsky publicó un trabajo en el que se describen las propiedades de los tipos de los lenguajes formales y sus correspondientes gramáticas con relación a la complejidad computacional. Según Chomsky, existen tres tipos de lenguajes formales: estados finitos o regulares, estructura de frase o libres de contexto y transformacionales o sensibles al contexto. Esta clasificación es conocida como la jerarquía de Chomsky.

El principal objetivo de la jerarquía de Chomsky fue demostrar que los dos primeros tipos de gramáticas son incapaces de dar cuenta, de manera simple y general, de la complejidad de las lenguas naturales. En particular, se demostró que el inglés presenta propiedades que no pueden ser reflejadas ni por gramáticas de estados finitos ni por gramáticas de estructuras de frase.

[pic 5]

Gramáticas de tipo 0

Una gramática de tipo 0 se denomina G0, o no restringida y es una gramática, que no tiene restricción alguna en sus leyes o reglas de producción. Se llama también gramática de un lenguaje estructurado por frases y gramática general estructurada por frases.

En ellas existe un axioma o símbolo de inicio que es un no terminal, y además en la parte izquierda de sus producciones tiene que haber al menos un símbolo no terminal y para la parte derecha no restricciones. Sus reglas de producción son del tipo:

P = { u → v |  u = xAy ∧ u ∈ E+ ∧ v, x, y ∈ E*∧ A ∈EA}

Una propiedad fundamental para identificar este tipo de gramáticas es que, si entre las reglas de producción de la gramática existe una que hace decrecer la longitud de la cadena, la gramática será indiscutiblemente de tipo 0.

En relación con los lenguajes que representan este tipo de gramáticas, si un lenguaje generado por una G0 es reconocible, su reconocedor puede ser una máquina de Turing.

Gramáticas de tipo 1

Una gramática de tipo 1, G1, o de sensible al contexto es una gramática cuyas leyes tienen la forma:

αAβ → αγβ, con A ∈ EA

Donde α, β, γ son cadenas; y ≠ λ; pero α y β pueden ser vacías; el par (α, β) se llama contexto.

Las partes izquierda y derecha tienen que tener una parte común y solo se admite como regla compresora la regla S → λ. Así, las reglas de producción que se describen son del tipo:

P = { (S → λ) o ( αAβ → αγβ)  | A ∈ EA ∧ α,β ∈ E*  ∧ γ ∈ E+}

Se denominan gramáticas dependientes del contexto porque se tiene en cuenta lo que viene antes y después del símbolo que se sustituye. Así en la fórmula anterior, α y β son el contexto de la transformación de A en γ. La característica de estas gramáticas es que las derivaciones producidas por la aplicación de sus reglas cumplen que las palabras tienen longitud mayor o igual que las anteriores en la derivación.

Si α1 → α2 → ⋯ → αn, entonces | αi | ≤ | α( i + 1 ) | ≤ | αn|, 1  ≤  i  ≤ n.

La recíproca también es cierta por el siguiente teorema: Para toda G con reglas de longitud no decreciente existe otra G’ equivalente a G, cuyas reglas son sensibles al contexto.

Gramáticas de tipo 2

Una gramática de tipo 2, G2, o de contexto libre es cualquier gramática cuyas leyes tienen la forma:

A → α, ( α ≠ λ, A ∈ EA)

Algunos autores aceptan también que α = λ.

Para estas gramáticas, la parte izquierda de las producciones solo puede tener un símbolo no terminal:

P = { (S → λ) o (A→α)  |  A ∈ EA ∧  ∈ E+}

Estas gramáticas también se llaman de contexto libre, ya que al transformar una palabra en otra, el símbolo no terminal que se transforma no depende de los que estén a la derecha o a la izquierda. Por lo tanto, cuando se realizan derivaciones en las que se transforme el símbolo a (en la producción anterior), no hace falta saber que hay antes o después de ese símbolo.

El estudio de los lenguajes producidos por las gramáticas de tipo 2 y el autómata reconocedor más indicado es el autómata de pila.

Gramáticas de tipo 3

Una gramática de tipo 3, G3 o regular es cualquier gramática cuyas leyes tienen la forma:

A → aB

O bien:

A → Ba

Y la forma:

A → a

Con a ∈ E = ET o bien a= λ.

Estas gramáticas son las más restrictivas y pueden ser de dos tipos:

1. Lineales por la izquierda, cuando cumplen:

P = { (S → λ)  o ( A→ Ba )  o ( A → a) | A,B ∈ EA ∧  a ∈ ET}

1. Lineales por la derecha cuando cumplen:

P = { (S → λ)  o ( A→ aB )  o ( A → a) | A,B ∈ EA ∧  a ∈ ET}

Conocidos los cuatro tipos de gramáticas presentados en el presente informe, se puede enunciar el teorema de jerarquía gramatical que dice:

G(i+1) ⊂ Gi, i = 0, 1, 2

Es decir:

G3 ⊂ G2 ⊂ G1 ⊂ G0

Máquina de Turing

[pic 6]

Alan Turing (1912-1954), el creador de las máquinas de Turing, fue un científico inglés que hizo importantes aportaciones matemáticas, de criptoanálisis, lógica, filosofía, biología, computación, inteligencia artificial y vida artificial.

Es considerado uno de los padres de la ciencia de la computación.

Una Máquina de Turing (MT), es un dispositivo hipotético que puede considerarse una cinta infinita dividida en casillas, cada una de las cuales contiene un símbolo. Sobre dicha cinta actúa un dispositivo que puede adoptar diversos estados y que, en cada instante, lee un símbolo de la casilla sobre la que está situado. En función del símbolo que ha leído y del estado en que se encuentra, realiza las tres acciones siguientes: pasa a un nuevo estado, imprime un símbolo en lugar del que acaba de leer, y se desplaza una posición hacia la izquierda, o hacia la derecha, o bien la máquina se para.

...