07:00
00
Temas Definición de Gramáticas de Estructura de Frase Proceso de derivación Gramáticas equivalentes Lenguajes de Estructura de Frase Jerarquía de Chomsky Relación entre los lenguajes
Objetivo Que el estudiante logre: Conocer, comprender y manejar conceptos vinculados con las Gramáticas de estructura de frase. Definir y reconocer gramáticas y lenguajes . 07:00
11
Símbolo: es simplemente una representación distinguible de cualquier información.
Alfabeto o Vocabulario: es un conjunto finito y no vacío de símbolos arbitrarios (símbolos terminales). V = {a1 , a2 , ... , an } Hilera: es cualquier string de longitud finita compuesto por símbolos sobre el vocabulario. Es un conjunto finito de símbolos yuxtapuestos. x es una hilera sobre V, si y solo si x = x1 … xn donde xi V, i = 1, …, n
Lenguaje: es un conjunto arbitrario de hileras de V* y se denota L. 07:00
22
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. 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*. S: Símbolo inicial o cabeza del lenguaje. Se lo usa para comenzar las derivaciones de las palabras del lenguaje. S VN. 07:00
33
VT = {a, b} VN= {S, A} P es: S aS S bA A bA A S es el símbolo distinguido
G = ({S,A}, {a,b}, { S aS / bA, A bA / }, S)
07:00
44
Una gramática genera un lenguaje de la siguiente manera: Comience con una hilera, llamada hilera en mano, consistente del símbolo distinguido solamente. 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
07:00
Hilera
Producción
S
S aA
aA
A aA
aaA
A bB
aabB
Bb
aabb 55
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 y (VNVT)* se dice que es derivable de en un paso ( ), si y solo si, hay palabras 1 y 2 en (VN VT)* y una producción A B en P tal que:
= 1 A 2 y = 1 B 2
07:00
66
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 α = β.
Ejemplo G = ({S}, {0,1}, P, S) donde P es: 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). 07:00
Por lo tanto: L(G) = { 0n 1n / n 1}
77
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.
07:00
88
Dos gramáticas G1 y G2 son equivalentes cuando generan el mismo lenguaje. L(G1) = L(G2) Nota:
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. 07:00
99
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 0 son los únicos terminales en L(G). Por lo tanto: L(G) = {an bn cn / n 0} 07:00
10 10
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) = . 07:00
11 11
A veces se utiliza una notación especial para describir gramáticas llamada notación BNF (Backus-Naus-Form). 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 →.
1) S aSa 2) S b
BNF 1) ::= aa 2) ::= b
Se tiene también la notación BNF-extendida que incluye además los símbolos [ ] y { } para indicar elementos opcionales y repeticiones, respectivamente. 07:00
12 12
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). 07:00
13 13
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. También es fundamental su contribución al establecimiento del ámbito de las ciencias cognitivas.
Avram Noam Chomsky (1928)
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.
07:00
14 14
: Las producciones son de la forma: donde
V* VN V* V* Generan lenguajes llamados Conjuntos Recursivamente enumerables. 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 07:00
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. 15 15
Las producciones son de la forma: z1Az2 z1Xz2
donde 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.
07:00
16 16
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
x=abc S T abD abc
x=aabbcc S T aTBD aabDBD aabABD aabADD aabBDD aabbDD aabbcc
Genera: L(G) = {an bn cn / n
0}
Obsérvese que si bien se presenta S , S no aparece en la parte derecha y que || || para las producciones. 07:00
17 17
Las producciones son de la forma: A donde A VN V* Generan lenguajes llamados Libres de Contexto.
Punto de vista teórico Punto de vista práctico
07:00
Las Gramáticas Libres de Contexto se relacionan con los Autómatas de Pila.
Los lenguajes de programación están basados en Lenguajes Libres de Contexto y Gramáticas Libres de Contexto. 18 18
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. Ejemplo 2: G = ({S}, {a,b,c}, S ,P) donde P es: S aSa / bSb / c 07:00
Sc S aSa aca S bSb bcb S aSa abSba abcba S aSa aaSaa aabSbaa aabcbaa
Genera L(G) = { wcw-1/ w {a,b}*}19 19
Las producciones son de la forma: – Gramáticas Lineales Izquierda A Ba donde A,B VN Ab b VT a VT – Gramáticas Lineales Derecha A aB donde A,B VN Ab b VT a VT
Generan lenguajes llamados Regulares. 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. 20 07:00 20
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 abA abbA abbb 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} 07:00
21 21
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
Tipo 0
Tipo 1
Tipo 2
Tipo 3
Las inclusiones son propias porque existe al menos un lenguaje de tipo k que no es de tipo k+1. 07:00
22 22
Generan
Lenguajes
Gramáticas
Jerarquía de Chomsky
Gramática no restringida
Lenguaje recursivamente enumerables
Gramática sensible al contexto
Lenguaje sensible al contexto
Gramática libre de contexto
Lenguaje libre de contexto
Gramática regular
Lenguaje regular
07:00
23 23
