1. Gramática Generativa De Chomsky.

Resumen

1.      INTRODUCCION

Esta investigación está basada en la materia de “AUTOMATAS Y LENGUAJES FORMALES” que tiene como fin conocer la manera en que funcionan los autómatas, y como se expresan en un determinado lenguaje computacional, con respecto a los aportes que realizo Avram Noam Chomsky.

Avram Noam Chomsky, nacido el 7 de diciembre de 1928 en Filadelfia, Estados Unidos, es un profesor emérito de Lingüística en el Massachusetts Institute of Technology (MIT), y una de las figuras más destacadas de la lingüística del siglo XX, con grandes aportaciones en el campo de la informática. Entre su contribución con la informática están sus enormes aportaciones a la Teoría de Autómatas y al estudio de los lenguajes formales. Puesto que han resultado elementos indispensables para la construcción de compiladores y traductores que puedan servir de intérpretes válidos entre las órdenes que dan los seres humanos y su correcta recepción y aplicación por máquinas automáticas

El contenido que aborda la investigación es acerca de la “Gramática de Generativa de Chomsky”, que nos menciona desde el punto de vista de la teoría de autómatas el conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a la Gramática de Chomsky, así como la clasificación de la Gramática que realizó con el paso del tiempo en las investigación que realizo acerca de los autómatas.

Además también se proporciona en esta investigación la “Forma Normal de Chomsky”; este tema se centra en los lenguajes libre de contexto, estos son conjuntos finitos de variables y terminales. La Forma Normal de Chomsky nos da a conocer una manera en la que podemos resolver una autómata y también cual puede ser el funcionamiento que realiza el mismo. También se explica la manera en que funcionan los autómatas de cerraduras, este es parecido al AFN a diferencia que la función de transición debe incluir información sobre las transiciones, que se representa por medio de un conjunto.

La última parte de la investigación nos permite conocer cómo funciona un autómata de pila, de igual forma, se proporciona la gramática que posee este autómata, entre otros aspectos importantes que hacen referencia a un autómata de pila.

Todos estos temas tienen relevancia en esta materia pues nos permiten conocer más acerca de los autómatas y las diferencias que existen entre un autómata y otro, además permite una mejor comprensión de las gramáticas libres de contexto, y la relación que existe entre los autómatas. Así mismo, nos ayudan a conocer la importancia que tienen las gramáticas en los autómatas.

2.      GRAMATICA GENERATIVA DE CHOMSKY

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 gramáticas equivalentes.

Una gramática es una estructura algebraica formada por cuatro elementos fundamentales:

G = {V, T, S, P}

Donde:

·         V es el conjunto de elementos No Terminales

·         T es el conjunto de elementos Terminales

·         S es el Símbolo inicial de la gramática

·         P es el conjunto de Reglas de Producción

2.1. JERARQUIA DE CHOMSKY

2.1.1.      TIPO 0  “LENGUAJE NO RESTRINGIDO O RECURSIVAMENTE ENUMERABLES”

x à y

x € ( NT | T)⁺

y € ( NT | T)*

“x puede ser sustituido por y si x está, ya sea, en los símbolos No Terminales o los símbolos Terminales, sin incluir la cadena vacía e y está en los símbolos No Terminales o Terminales, incluyendo la cadena vacía.”

Los lenguajes generados por este tipo de gramáticas se llaman "lenguajes sin restricciones"

Nota: "+" significa "sin incluir la cadena vacía" y "*" significa "incluyendo la cadena vacía". "/" significa "o"

Estos lenguajes también son denominados "recursivamente enumerables".

TIPO DE AUTOMATA: MAQUINA DE TURING

2.1.2.      TIPO 1 “LENGUAJE SENSIBLE AL CONTEXTO”

α à β; | α | ≤ | β |

α = z₁ x z₂

β = z₁ y z₂

z₁, z₂ € T*

x € NT

y € ( NT | T )⁺

“α puede ser reemplazado por β si la longitud de α es menor o igual a la longitud de β, siendo α un símbolo Terminal o una cadena vacía z₁, seguido de un símbolo No Terminal X, seguido de otro símbolo Terminal o una cadena vacía z₂. En el caso de β, z₁ debe ser el mismo símbolo z₁ de α seguido de un símbolo No Terminal o Terminal sin ser la cadena vacía, seguido del símbolo z₂.”

TIPO DE AUTOMATA: AUTOMATAS LINEALMENTE ACOTADOS

2.1.3.     TIPO 2 “LENGUAJE LIBRE DE CONTEXTO”

xà y

x € NT

y € (NT|T)*

“x puede ser reemplazado por y si x pertenece a los símbolos No Terminales e y es un Terminal o No Terminal, incluyendo la cadena vacía.”

TIPO DE AUTOMATA: AUTOMATA PILA

2.1.4.      TIPO 3 “LENGUAJE REGULAR”

α à β

α € NT

B € NT

a € T⁺

b € T*

También llamada "De contexto regular"

“α puede ser reemplazado por β si α pertenece a los símbolos No Terminales y β es uno de estos 3:

·         Un símbolo Terminal no nulo seguido de un No Terminal.

·         Un símbolo No Terminal seguido de un símbolo Terminal no nulo.

·         Un símbolo Terminal pudiendo ser la cadena vacía.”

TIPO DE AUTOMATA: AUTOMATA FINITO

3.      FORMA NORMAL DE CHOMSKY

TEOREMA:

(Forma Normal de Chomsky o CNF) cualquier lenguaje libre de contexto sin €, es generado por una gramática en la que todas las producciones son de la forma Aà BC o Aà a. Aquí, A, B y C son variables y a es una terminal.

DEMOSTRACION:

Sea G una gramática libre de contexto que genera un lenguaje que no contiene a €. Por el teorema, podemos encontrar una gramática equivalente, G₁ = (V, T, P, S), tal que P no contenga producciones unitarias o producciones €. Por tanto, si una producción tiene un símbolo simple a la derecha, ese símbolo es una terminal, y la producción se halla ya en una forma aceptable.

Ahora considérese una producción P de la forma AàX₁ X₂… X_m, en donde m ≥ 2. Si x, es una terminal a, introdúzcase una nueva variable C_a y una producción C_aàa, que es una forma permisible. Entonces sustituya X_i por C_a. Sea el nuevo conjunto de variables Vⁿ y sea el nuevo conjunto de producciones P¹. Considere la gramática G₂ = (V¹, T, P¹, S). Si α  β, entonces αβ. Por lo tanto L (G₁) Í L (G₂). Ahora mostraremos la inducción sobre el número de pasos de una derivada que si A W, para A en V y W en T*, entonces A  W. El resultado es trivial para derivaciones de un paso. Supóngase que es verdadera para derivaciones de hasta k pasos. Sea A W una derivación (k+1) pasos. El primer paso debe ser de la forma Aà B₁ B₂… B_m,  m ≥ 2. Podemos escribir W =  W₁ W₂… W_m en donde B_i  W_i, 1 ≤ i ≤ m.

Si B_i es C_ai para alguna terminal a_i, entonces W_i debe ser a_i, por la construcción de Pⁱ, existe una producción Aà X₁ X₂… X_m,  de P en la que X_i = B_i si B_i está en V y X_i=a_i si B_i esta V_i–V. Para este B_i en V, sabemos que la derivación B_i  W_i no toma más de k pasos, de modo que la hipótesis inducida X_i  W_i. En consecuencia, A W.

Hemos demostrado el resultado intermedio que consiste en que cualquier lenguaje libre de contexto puede ser generado por una gramática para la cual cada producción es de la forma Aàa o AàB₁ B₂… B_m, para m ≥ 2. Aquí A y B₁, B₂,…, B_m son variables, y a es una terminal.

Considérese dicha gramática G= (V¹, T, P¹, S). Modificamos G₂ mediante la adición de algunos símbolos más a V¹ y sustituyendo algunas producciones de P¹. Para cada producción AàB₁ B₂… B_m de P¹ en donde m ≥ 3, creamos nuevas variables D₁, D₂,.., D_m-2 y sustituimos AàB₁ B₂… B_m por el conjunto de producciones.

{AàB₁ D₁, D₁àB₂ D₂,…, B_m-3à B_m-2 D_m-2, D_m-2à B_m-1 B _m}

Sean Vⁿ el nuevo vocabulario no terminal  y Pⁿ el nuevo conjunto de producciones. Sea G₃=(Vⁿ, T, Pⁿ,V). G₃ está en CFN. Es claro que si Aβ, entonces Aβ de manera que L (G₂) Í L (G₃). Pero también es verdad que L (G₃) Í L (G₂), como puede mostrarse, esencialmente de la misma manera en que se mostró que L (G₂) Í L (G₁).

EJEMPLO:

Consideremos la gramática ({S, A, B}, {a,, b}, P, S) que tiene las producciones:

Sàb A | aB

Aàb AA | aS | a

Bàa BB | bS | b

Y encontremos una gramática equivalente en CNF.

Primero, las únicas producciones que ya se encuentran en forma apropiada son Aàa y Bàb. No existen producciones unitarias, así que podemos empezar sustituyendo las terminales de la derecha por variables, excepto en el caso de las producciones Aàa y Bàb. Sàb A se sustituye por SàC_b A y C_bàb. De manera similar, Aàa S se sustituye por AàC_a S y C_aàa; AàbA A es sustituida por AàC_b AA; Sàa B se reemplaza por SàC_a B; Bàb S es reemplazado por BàC_b S; y Bàa BB es sustituido por BàC_a BB.

En la siguiente etapa, la producción AàC_b AA se sustituye por AàC_b D₁ y D₁àAA y la producción BàC_a BB se reemplaza por BàC_a D₂ y D₂àBB. Las producciones para la gramática CNF se muestran a continuación:

SàC_b A | C_a B

AàC_a S | C_b D₁ | a

BàC_b S | C_a D₂ | b

D₁àAA

D₂àBB

C_aàa

C_bàb

  

4.      AUTOMATAS DE TRANSICION DE CERRADURAS

4.1.NOTACION FORMAL PARA UN AFN-€

Se puede representar un AFN-€ exactamente igual que un AFN, con una sola excepción: la función de transición debe incluir información sobre las transiciones €. Formalmente, representamos un AFN-€ A mediante A= (Q, ∑,d, q₀, F), donde las componentes tiene la misma interpretación que en un AFN, excepto d es ahora una función con dos argumentos:

1.      Un estado perteneciente a Q.

2.      Un miembro de ∑ È {€}, es decir, un símbolo de entrada o el símbolo €. Se exige que €, el símbolo que representa la cadena vacía, no forme parte del alfabeto ∑, para que no se produzca confusiones.

4.2.CLAUSURAS RESPECTO DE €

Formalmente, la clausura respecto de €, CLAUS_€ (q), se define recursivamente de la siguiente forma:

BASE: El estado q está en CLAUS_€ (q).

PASO INDUCTIVO: si el estado p está en CLAUS_€ (q) y existe una transición desde el estado p al estado r con la etiqueta €, entonces r está en CLAUS_€ (q). Con más precisión, si d es la función de transición del AFN-€ y p esta en CLAUS_€ (q), entonces CLAUS_€ (q) también contiene todos los estados de d(p, €).

4.3.TRANSICION Y LENGUAJES EXTENDIDOS PARA AFN-€

La clausura con respecto de € nos permite explicar fácilmente el aspecto de las transiciones de un AFN-€ cuando se tiene una secuencia de entradas que no contiene €.

Supongamos que E= (Q, ∑,d, q₀, F) es un AFN-€. Primero definiremos d, la función de transición extendida, para reflejar lo que ocurre con una secuencia de entrada. La idea es que d(q, w) es el conjunto de estados a los que se puede llegar mediante un camino cuyas etiquetas, concatenadas, formen la cadena w. Como siempre, los símbolos € que se encuentran a lo largo del camino contribuyen a w. La definición recursiva d es:

BASE: d(q, w)= CLAUS_€ (q). Es decir, si la entrada es €, solo podemos seguir aros con la etiqueta € que salgan del estado q, esto es exactamente lo que hace CLAUS.

PASO INDUCTIVO: Supongamos que w tiene la forma xa, donde a es un miembro de ∑; no puede ser €, porque no está en ∑. Calculamos d(q, w) de la siguiente forma:

1.      Sea {p₁, p₂,…, p_k} la función d(q, x). Es decir, los p_i son todos los estados que podemos alcanzar desde q siguiendo un camino cuya concatenación de etiquetas sea x, y solo estos. Este camino puede terminar con una o más transiciones con la etiqueta €, así como contener otras transiciones €.

2.      Sea  el conjunto {r₁, r₂,…, r_m}. Es decir, seguimos todas las transiciones con a etiqueta a a partir de los estados que podemos alcanzar desde q siguiendo caminos con la etiqueta x. Los r_j son algunos de los estados que podemos alcanzar desde q siguiendo caminos con la etiqueta w. Los estados adicionales que podemos alcanzar se obtienen a partir de los r_j siguiendo arcos con la etiqueta € en el paso 3.

3.      d(q, w)=  Este paso de clausura adicional añade todos los camino que paren desde q con la etiqueta w, teniendo en cuenta la posibilidad de que el autómata puede seguir arcos adicionales con la etiqueta € después de hacer una transición con el ultimo símbolo “real”, a.

4.4.ELIMINACION DE LAS TRANSICIONES €

Dado un AFN-€ E, se puede encontrar un AFD D que acepte el mismo lenguaje que E. La construcción  que vamos a utilizar es muy parecida a la construcción de subconjuntos, pues los estados de D son subconjuntos de los estados de E. La única diferencia es que hay que incorporar las transiciones € de E, lo que se hace mediante el mecanismo de la clausura respecto de €.

Sea E = (Q_E, ∑,d_E, q₀, F_E). El AFD equivalente se define así:

1.      Q_D es el conjunto de los subconjuntos de Q_E. De forma más precisa, los únicos estados accesibles de D son subconjuntos de Q_E cerrados respecto de €; es decir, los subconjuntos S Í Q_E tales S= CLAUS_€ (S). Dicho de otra forma, los conjuntos de estados de S cerrados respecto de € son aquellos para los que cualquier transición € que salga de uno de los estados que pertenecen a S lleva a otro estado que también pertenece a S. Nótese que Æ es un conjunto cerrado respecto a €.

2.      q_D= CLAUS_€ (q₀); es decir, el estado inicial de D se obtiene cerrando el conjunto que solo contiene el estado inicial de E. Nótese que esta regla difiere de la construcción de subconjuntos original, donde el estado inicial del autómata construido era el conjunto que solo contenía el estado inicial de AFN dado.

3.      F_D está formado por los conjuntos de estados que contiene al menos un estado de aceptación de E. Es decir, F_D= {S | s pertenece a Q_D, y S Ç F_E ¹Æ }.

4.      d_D(S, a) se calcula así para todo a perteneciente a ∑ y todo conjunto S perteneciente a Q_D:

a)      Sea S = {p₁, p₂,…, p_k}.

b)      Se calcula ; sea este conjunto {r₁, r₂,… r_m}.

c)      Entonces, d_D(S, a) = .

4.5.AUTOMATAS FINITOS CON TRANSICIONES €

PASO INDUCTIVO: Supongamos que w = xa, donde a es el símbolo final de w, y supongamos que la afirmación se cumple para x. Es decir, d_E (q₀, x)= d_D (q_D, x). Supongamos que estos dos conjuntos de estado son {p₁, p₂,…p_k}. Por la definición de d para los AFN-€, calculamos d_E (q₀, w) así:

1.      Sea {r₁, r₂,…, r_m} igual a _E (p_i,a).

2.      Entonces, d_E (q₀, w) = .

Si se examina la construcción de AFD D realizada más arriba mediante la construcción de subconjuntos modificada, vemos que d_D ({p₁, p₂,…, p_k}, a) se construye con los mismos pasos (1) y (2) anteriores. Por lo tanto, d_D (q_D, w), que es d_D ({p₁, p₂,…, p_k}, a), es el mismo conjunto que d_E (q₀, w). Hemos demostrado que d_E (q₀, w) = d_D (q_D. w), y se completa la parte inductiva.

5.      AUTOMATAS DE PILA

5.1.DEFINICION

Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky. Formalmente, un autómata con pila puede ser descrito como una séptupla  donde:

·          es un conjunto finito de estados;

·          y  son alfabetos (símbolos de entrada y de la pila respectivamente);

·        

·          es el estado inicial;

·          es el símbolo inicial de la pila;

·          es un conjunto de estados de aceptación o finales;

La interpretación de , con , y  es la siguiente:

Cuando el estado del autómata es , el símbolo que la cabeza lectora está inspeccionando en ese momento es , y en la cima de la pila nos encontramos el símbolo , se realizan las siguientes acciones:

·         Si , es decir no es la cadena vacía, la cabeza lectora avanza una posición para inspeccionar el siguiente símbolo.

·         Se elimina el símbolo  de la pila del autómata.

·         Se selecciona un par  de entre los existentes en la definición de , la función de transición del autómata.

·         Se apila la cadena , con  en la pila del autómata, quedando el símbolo  en la cima de la pila.

·         Se cambia el control del autómata al estado .

5.2.FUNCIONAMIENTO

Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO). Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.¹

5.3.AUTOMATA CON PILA DETERMINISTA

Nótese que, a diferencia de un autómata finito o una máquina de Turing, la definición básica de un autómata con pila es de naturaleza no determinista, pues la clase de los autómatas con pila deterministas, a diferencia de lo que ocurría con aquellos modelos, tiene una potencia descriptiva estrictamente menor. Para calificar a un autómata con pila como determinista deben darse dos circunstancias; en primer lugar, por supuesto, que en la definición de cada componente de la función de transición existan un único elemento lo que da la naturaleza determinista. Pero eso no es suficiente, pues además puede darse la circunstancia de que el autómata esté en el estado  y en la pila aparezca el símbolo , entonces, si existe una definición de transición posible para algún símbolo cualquiera  del alfabeto de entrada, pero, además existe otra alternativa para la palabra vacía , también esto es una forma de no determinismo, pues podemos optar entre leer un símbolo o no hacerlo. Por eso, en autómata determinista no debe existir transición posible con lectura de símbolo si puede hacerse sin ella, ni al contrario.

Para cada , se dé que:  , para cada 

Un autómata de pila determinista (AFPD) es una 7-upla,

P = (Q, Σ, Г,Δ, q0, T,Z) donde:

·         Q es un conjunto finito de estados.

·         Σ es el alfabeto de entrada.

·         Г es el alfabeto de la pila.

·         q0 є Q es el estado inicial.

·         Z є Г símbolo inicial de la pila.

·         T es subconjunto de Q (conjunto de estados finales).

·         Δ es la función de transición tal que:

         Δ: Q × (Σ U { ε }) × Г → (Q × Г *)

5.4.AUTOMATA CON PILA NO DETERMINISTA

Un autómata finito con pila no determinista (AFPN) consta de los mismos parámetros de un AFPD.

P = (Q, Σ, Г, Δ, q0, T,Z): Donde la función de transición Δ es de la forma:

       Δ: Q × (Σ U { ε }) × Г→ Pf(Q × Г*)

Donde Pf (Q× Г *) es un conjunto de subconjuntos finitos de Q × Г*. Para q є Q, a є Σ U {ε} y s є Г

       Δ (q, a, s) = {(q1, γ1), (q2, γ 2), . . . , (qn, γ n)}

Donde γi є Г*

EJEMPLO

Diseñar un AFPN que acepte el lenguaje ⁴

Sobre:

Σ = {a, b}

·         Δ (q0, a, Z) = (q0, AZ)

·         Δ (q0, ε, Z) = (q2, Z) (acepta ε)

·         Δ (q0, a, A) = (q0, AA)

·         Δ (q0, b, A) = (q1, ε)

·         Δ (q1, b, A) = (q1, ε)

·         Δ (q1, ε, Z) = (q2, Z)

6.      FICHAS BIBLIOGRAFICAS

·         HOPCROFT, John E.; ULMAN, Jeffrey D.,” INTRODUCCION A LA TEORIA DE AUTOMATAS, LENGUAJES FORMALES Y COMPUTACION”, Primera Edición, 1993; edit. CECSA, pág. 100-101.

·         HOPCROFT, J.E.; MOTWANI, R.; ULLMAN, J.D.; “INTRODUCCION A LA TEORIA DE AUTOMATAS, LENGUAJES Y COMPUTACION”; Segunda Edición, 2002; edit. PEARSON EDUCACION; pág. 79-87.

CIBERGRAFIAS

·         http://es.wikipedia.org/wiki/Gram%C3%A1tica_%28aut%C3%B3mata%29

·         https://www.academia.edu/8475322/Jerarquia_de_Chomsky_y_Fases_de_un_compilador

·         http://www.ia.urjc.es/grupo/docencia/automatas_itis/apuntes/capitulo11.pdf

·         http://www.dialnet.unirioja.es/descarga/articulo/2580734.pdf

·         http://users.dsic.upv.es/asignaturas/facultad/tdl/apila.pdf

·         http://es.wikipedia.org/wiki/Aut%C3%B3mata_con_pila