Lenguajes Formales y Gramáticas

Programación II

Margarita Álvarez

Gramática de Estructura de Frase 

Si un lenguaje contiene solamente un número finito de hileras dicho lenguaje se lo puede definir por comprensión o extensión.  Si el lenguaje es infinito se lo define mediante un mecanismo matemático finito denominado gramática de estructura de frase.  Una gramática es, básicamente, un sistema de reglas o producciones que controlan el orden en que los elementos pueden aparecer en el lenguaje.  La gramática provee un dispositivo para definir las estructuras de las sentencias del lenguaje y un mecanismo de aceptación el cual permite determinar si la hilera pertenece o no al lenguaje.  La clase de lenguajes que generan se denomina lenguajes de estructuras de frase.

Gramática de Estructura de Frase Es un sistema:  

G = (VN, VT, P , S) VN es el vocabulario no terminal VT es el vocabulario terminal 

donde:

Ambos vocabularios son finitos y no vacíos V = VN  VT

y

VN  VT = 



P: conjunto de producciones o reglas de reescritura.  S: Símbolo inicial o cabeza del lenguaje. Se lo usa para comenzar las derivaciones de las palabras del lenguaje. S VN. Ejemplo G = ({S,A}, {a,b}, { S  aS / bA A  bA / }, S)

Gramática de Estructura de Frase 

VN: es el vocabulario no terminal de símbolos introducidos como elementos auxiliares para la definición de la gramática y que no figuran en las hileras del lenguaje. Se lo denomina también metalenguaje y se los denota con letras mayúsculas. Ejemplo VN= {S, A}

Gramática de Estructura de Frase 

VT: es el vocabulario terminal: Todas las sentencias del lenguaje definidas por la gramática están formadas con los símbolos o caracteres de VT. Ejemplo VT = {a, b}

Gramática de Estructura de Frase 

P: conjunto de producciones o reglas de reescritura. Es un conjunto finito de V+ x V*, o sea que es un conjunto de pares ordenados tales que P y Q están en (VN  VT)* y P contiene al menos un símbolo de VN. Las producciones son de la forma   , donde   V* VN V* y  V*. P = {α → β / α V* VN V*,β  V* }



Son usadas para derivar nuevas palabras desde otra dada, reemplazando el lado izquierdo por la regla del lado derecho. Ejemplo S  aS / bA A  bA / 

Proceso de Derivación Una gramática genera un lenguaje de la siguiente manera: a) Comience con una hilera, llamada hilera en mano, consistente del símbolo distinguido solamente. b) Aplicar las producciones de P a la hilera en mano hasta que conste únicamente de símbolos terminales.

Ejemplo G = ({S,A,B}, {a,b}, P,S) donde P es: S  aA A  aA / bB B  bB / b

Hilera en mano

Producción aplicada

S

S  aA

aA

A  aA

aaA

A  bB

aabB

B  bB

aabbB

B  bB

aabbb

Bb

Proceso de Derivación El proceso de usar una gramática para generar hileras se denomina derivación. Derivación en un solo paso Dada una gramática G = (VN, VT, P, S) y dos palabras X y Y(VN  VT)* se dice que Y es derivable de X en un paso (X  Y), si y sólo si, hay palabras P1 y P2 en (VN  VT)* y una producción P  Q en P tal que: G X = P1 P P2 y Y = P1 Q P2

Derivación en cero o más pasos

Es el cierre reflexivo y transitivo de G y se denota con G *. Se dice que α G * β si existe una sucesión de cadenas intermedias φ1,φ2, ..., φn, tales que: α = φ1 G φ2 ... G φn = β. Si n = 0 entonces α = β.

Proceso de Derivación - Ejemplo Sea G = ({S}, {0,1}, P, S) donde P consta de las siguientes producciones: 1)

S  0S1

2)

S  01

Usamos la producción (1) n-1 veces y se llega a: S * 0n-1 S 1n-1 Luego, se usa la regla (2), 1 vez y se llega a: S * 0n 1n

Las palabras 0n 1n con n  1 son los únicos terminales en L(G). Por lo tanto: L(G) = { 0n 1n / n  1}

Proceso de Derivación - Ejemplo Sea G = ({S,B,C}, {a,b,c}, P, S) donde P consta de las siguientes producciones: Usamos la producción (1) n-1 veces y se llega a: 1)

S  aSBC

2)

S  aBC

3)

CB  BC

4)

aB  ab

5)

bB  bb

6)

bC  bc

7)

cC  cc

S * an-1 S(BC)n-1 Luego, se usa la regla (2), 1 vez y se llega a: S * an (BC)n Se aplica la producción (3) n veces y se llega a: S * an Bn Cn Se aplica la producción (4) una vez y se obtiene: S * an bBn-1 Cn Se aplica la producción (5) n-1 veces y se llega a: S * an bn Cn Se aplica la producción (6) una vez y la regla (7) n-1 veces y se llega a: S * an bn cn

Las palabras an bn cn con n  1 son los únicos terminales en L(G). Por lo tanto: L(G) = { an bn cn / n  1}

Gramáticas Equivalentes Dos gramáticas G1 y G2 son equivalentes cuando generan el mismo lenguaje: L(G1) = L(G2). Observaciones:  La equivalencia de gramáticas es una propiedad indecidible, y por tanto, cualquier otro problema que pueda plantearse como tal.  Es posible demostrar equivalencia entre dos gramáticas particulares. Lo que no puede darse es un método general de prueba único para cualquier par de gramáticas.

Gramáticas Equivalentes - Ejemplo Sea G = ({S,A,B}, {a,b,c}, P, S) donde P consta de las siguientes producciones: 1) S  Abc 2) Ab  aAbB 3) Bb  bB 4) Bc bcc 5) A  a

Usamos la producción (1) una vez y se aplica la producción (2) n-1 veces con lo que se llega a: S * an-1 AbBn-1c Luego, se usa la regla (5), una vez y se llega a: S * an-1 abBn-1c o sea S * anbBn-1c Se aplica la producción (4) n-1 veces y la regla (3) n-2 veces en forma alternada y se llega a: S * an bn cn

Las palabras an bn cn con n  1 son los únicos terminales en L(G). Por lo tanto: L(G) = { an bn cn / n  1}

Lenguaje de Estructura de Frase El lenguaje generado por G, se define como: *

L(G) = {p  VT / S  p} G

Esto significa que el lenguaje generado por G contiene exactamente aquellas palabras que son derivables del símbolo inicial S y contiene únicamente símbolos terminales.

Lenguaje Vacío Es el lenguaje que no contiene ninguna hilera, se genera mediante cualquier gramática que no genera ninguna hilera. Ejemplo G = ({S}, {a}, {S  aS}, S) Proceso de Derivación S  aS  aaS  aaaS  ….. Esta gramática genera hileras de la forma akS con k = 1, 2, ... pero como ninguna de ellas consta de símbolos terminales únicamente, entonces L(G) = .

Notación BNF A veces se utiliza una notación especial para describir gramáticas llamada notación BNF (Backus-NausForm). En la notación BNF los símbolos no terminales o variables son encerrados entre ángulos y se utiliza el símbolo ::= para las producciones, en lugar de →. Ejemplo: la producción S → aSa se representa en BNF como S ::= a S a. Se tiene también la notación BNF-extendida que incluye además los símbolos [ ] y { } para indicar elementos opcionales y repeticiones, respectivamente.

Jerarquía de Lenguajes y Gramáticas de Estructura de Frase

Se llama “clase de lenguajes” a conjuntos de lenguajes que comparten una cierta propiedad dada. Esta noción es muy abstracta, pues ya los lenguajes son en sí mismos conjuntos de secuencias de símbolos, y las clases de lenguajes son entonces conjuntos de conjuntos de secuencias de símbolos.  La clasificación de lenguajes en clases de lenguajes es debida a N. Chomsky, quien propuso una jerarquía de lenguajes, donde las clases más complejas incluyen a las más simples. Esto se logra estableciendo ciertas restricciones en los elementos de P (reglas de producción). 

Avram Noam Chomsky 



  



Avram Noam Chomsky (1928) es profesor emérito de Lingüística en el MIT y una de las figuras más destacadas de la lingüística del siglo XX. Creó la gramática generativa, disciplina que situó la sintaxis en el centro de la investigación lingüística y con la que cambió por completo la investigación en el estudio del lenguaje. Postuló el innatismo y la autonomía de la gramática (sobre los otros sistemas cognitivos). También es fundamental su contribución al establecimiento del ámbito de las ciencias cognitivas. Se le considera creador de la jerarquía de Chomsky, una clasificación de lenguajes formales de gran importancia en teoría de la computación. Muy conocido por su activismo político y sus duras críticas a la política exterior de EE.UU. y de otros países, como el Estado de Israel.

Avram Noam Chomsky (1928)

Jerarquía de Lenguajes y Gramáticas de Estructura de Frase Tipo 0: Gramáticas de estructura de frase no restringida o general Las producciones son de la forma:   

donde

  V* VN V*  V*

Generan lenguajes llamados Conjuntos Recursivamente enumerables

Tipo 0 - Ejemplo Sea G = ({S,A, B,C,D,E},{a},P,S) donde P es: S  ACaB Ca  aaC CB  DB / E aD  Da AD  AC aE  Ea AE  

x=aa S  ACaB  AaaCB  AaaE  AaEa  AEaa aa

Genera el lenguaje L(G) = { a2i / i  1} Como se observa no existen restricciones sobre las producciones.

Jerarquía de Lenguajes y Gramáticas de Estructura de Frase Tipo 1: Gramáticas de estructura de frase sensibles al contexto Las producciones son de la forma: 

z1Az2  z1Xz2

z1, z2  V* A  VN X  V+ Se admite sólo S  , pero S no debe aparecer en el lado derecho de ninguna producción. Se impone la siguiente condición a las producciones:        Generan lenguajes llamados Sensibles al Contexto. donde

Tipo 1- Ejemplo G = ({S,T,B,C,D} , {a,b,c} ,S, P} donde P es:

S /T T  aTBD / abD DB  AB AB  AD AD  BD bB  bb D c

Genera: L(G) = {an bn cn / n



0}

x=abc S  T  abD  abc x=aabbcc S  T  aTBD  aabDBD  aabABD  aabADD  aabBDD  aabbDD  aabbcc

Obsérvese que si bien se presenta S   , S no aparece en la parte derecha y que ||  || para las producciones.

Jerarquía de Lenguajes y Gramáticas de Estructura de Frase Tipo 2: Gramáticas de estructura de frase libres al contexto Las producciones son de la forma: A   donde A  VN   V* Generan lenguajes llamados Libres de Contexto. Estos lenguajes son importantes tanto desde el punto de vista teórico, por relacionar las llamadas Gramáticas Libres de Contexto con los Autómatas de Pila, como desde el punto de vista práctico, ya que casi todos los lenguajes de programación están basados en los lenguajes libres de contexto. En efecto, a partir de los años 70’s, con lenguajes como Pascal, se hizo común la práctica de formalizar la sintaxis de los lenguajes de programación usando herramientas basadas en las Gramáticas Libres de Contexto, que representan a los lenguajes libres de contexto. Por otra parte, el análisis automático de los estos lenguajes es computacionalmente mucho más eficiente que el de otras clases de lenguajes más generales.

Tipo 2 - Ejemplo Ejemplo 1: G = ({S}, {a,b}, S ,P) donde P es: S  aSb / 

S  S  aSb  ab  S  aSb  aaSbb  aabb  S  aSb  aaSbb  aaaSbbb  aaabbb

Genera L(G) = { an bn/ n  0}

Obsérvese que a la izquierda de la regla hay sólo un no terminal y a la

derecha de la regla no terminales y/o terminales. Sc Ejemplo 2:  S  aSa  aca  S  bSb  bcb G = ({S}, {a,b,c}, S ,P)  S  aSa  abSba  abcba donde P es:  S  aSa  aaSaa  aabSbaa  aabcbaa S  aSa / bSb / c

Genera L(G) = { wcw-1/ w {a,b}*}

Jerarquía de Lenguajes y Gramáticas de Estructura de Frase

Tipo 3: Gramáticas de estructura de frase regulares Las producciones son de la forma: 

Gramáticas Lineales Izquierda

A  Ba Ab 

donde

A,B  VN b  VT   a  VT

Gramáticas Lineales Derecha

A  aB Ab

donde

A,B  VN b  VT   a  VT

Nota: en una misma gramática no pueden aparecer producciones de ambos tipos.

Generan lenguajes llamados Regulares.

Tipo 3 - Ejemplo Gramática lineal derecha G1 = ({S,A} , {a,b}, S , P) donde P es: S  aS / bA /  A  bA /  S  S  aS  a  S  aS  aaS  aabA  aabbA  aabbbA  aabbb  S  bA  bbA  bbbA  bbb

Gramática lineal izquierda G2 = ({S,A} ,{a,b} , S , P) donde P es: S  Sb / Aa /  A Aa /  S  S  Aa  a  S  Sb  Sbb  Aabb  abb  S  Aa  Aaa  Aaaa  aaa

Ambas gramáticas generan: L(G) = {ai bj / i  0, j  0} Propiedad: a toda gramática G lineal regular derecha (izquierda) le corresponde otra gramática G' lineal regular izquierda (derecha) tal que: L(G') = L(G). Es decir, un lenguaje se genera mediante una gramática regular lineal derecha si y sólo si, se genera por alguna gramática lineal izquierda.

Relación entre Lenguajes Un lenguaje de estructura de frase se dice de tipo k (k=0,1,2,3) si existe una gramática de tipo k que lo genere. Sea Lk el conjunto de lenguajes de estructura de frase de tipo k. Entonces se tiene que: L3  L2  L1  L0

L3 L2 L1 L0

Las inclusiones son propias porque existe al menos un lenguaje de tipo k que no es de tipo k+1.