|
||||||
NOTACIÓN |
|
GRAMÁTICAS GENERATIVAS | ||||
OPERACIONES CON LENGUAJES. |
|
LENGUAJE GENERADO POR UNA GRAMÁTICA | ||||
JERARQUÍA DE CHOMSKY | EJEMPLOS QUÉ LENGUAJE GENERAN LAS SIGUIENTES GRAMÁTICAS? |
|
||||||
LENGUAJE GENERADO POR UNA GRAMÁTICA | ||||||
Dada la definición de la gramática con la cuádrupla especificada anteriormente podemos generar las distintas palabras que corresponde al lenguaje de esa gramática. Esta generación se hace mediante el siguiente PROCESO: | ||||||
Para generar las palabras del lenguaje comenzamos en el símbolo inicial S y vamos aplicando sucesivamente las reglas de producción (P) de la gramática especificada, de forma que vamos a ir obteniendo secuencias de símbolos terminales distintas en función de cual sea la regla aplicada en cada paso. | ||||||
Para establecer la idea de una forma rigurosa vemos las siguientes definiciones y ejemplos preliminares: | ||||||
DEFINICION: | ||||||
Dada
una gramática G=(V, T, P,S) y dos palabras a
, b ∈(V∪
T)*,
decimos
que b
es derivable a partir de a
en un paso (ab
) si y solo si existen palabras
d1,d2∈(V∪
T)* una
producción sj
tales que a
=d1s
d2,
b=d1jd2. |
||||||
Ejemplo: | ||||||
Haciendo referencia a la gramática del ejemplo anterior, tenemos las siguientes derivaciones: | ||||||
E E + E (E) + E (E) + (E) (E*E) + (E) (E*E) + (E*E) | ||||||
DEFINICION: | ||||||
Dada
una gramática G=(V, T, P,S) y dos palabras a
, b ∈(V∪
T)*, decimos que b
es derivable de a
en un paso (a
* b)si
y solo si existen una sucesión de palabras d1,
..., d2(n
=1) tales que a
=d 1⇒
d2⇒ ....... ⇒n=b |
||||||
Ejemplo: | ||||||
En el caso anterior podemos decir que (E*E) + (E*E) es derivable a partir de E: | ||||||
E ⇒*(E*E) + (E*E) | ||||||
DEFINICION: | ||||||
Se
llama lenguaje generado por una gramática
G =(V,T,P,S) al conjunto de cadenas formadas por símbolos terminales
y que son derivables a partir del símbolo de partida S.
Es decir L(G)={u ⇒ T*/ S ⇒* u}. |
||||||
EJEMPLO | ||||||
En el caso de la gramática de los ejemplos anteriores (E*E)+(E*E) no pertenece al lenguaje generado por G, ya que hay símbolos que no son terminales. Sin embargo (a+c)*(a+b) si pertenece a L(G), ya que se puede comprobar que es derivable a partir de E (símbolo de partida) y solo tiene símbolos terminales. | ||||||
NOTAS | ||||||
Si en una gramática comenzamos a hacer derivaciones a partir del símbolo original S, dicha derivación acabará cuando: | ||||||
Sólo queden símbolos terminales, en cuyo caso la palabra resultante pertenece a L(G). | ||||||
O cuando queden variables pero no se pueda aplicar ninguna regla de producción, en cuyo caso dicha derivación no puede llevar a ninguna palabra de L(G). | ||||||
En general, cuando estemos haciendo una derivación puede haber más de una regla de producción aplicable en cada momento. | ||||||
Si
la gramática con la que estamos trabajando está clara eliminaremos
el signo * de la derivación de varios pasos, es decir, en vez de
escribir
a⇒ *b escribiremos a⇒ . |
||||||
|
2.- Sea G={V,T,P,S} una gramática donde el símbolo inicial es S , V={S,X,Y}, T={a, b,c} y las reglas de producción las siguientes: | |||
S→ abc, S→aXbc | Xb→ bX | Xc→ Ybcc | ||
bY→ Yb | aY→ aaX ,aY→aa |
|
JERARQUÍA DE CHOMSKY | |||
La Jerarquía de Chomsky es una clasificación de las gramáticas en función de la forma de éstas. | ||||
GRAMÁTICA DE TIPO 0 O CON ESTRUCTURA DE FRASE: cualquier gramática, sin restricciones. Un ejemplo de este tipo es la gramática que define el lenguaje español. | ||||
GRAMÁTICA DE TIPO 1 O DEPENDIENTES DEL CONTEXTO: si todas las producciones tienen la forma: | ||||
a1Aa2→a1βa2 donde
a1a2β ∈
(V∪
T)*, A ∈
V, β ≠ε,
excepto
posiblemente la regla S→ε,
en
cuyo caso S no aparece a la derecha de las reglas.
(el
precedente de la implicación tiene una variable A precedida o seguida
por un símbolo del alfabeto)
Un ejemplo de este tipo de gramática de tipo 1 es el siguiente: G=({S,X,Y} {a, b, c}, P, S ) donde las producciones P son S abc, aXbc Xb bX Xc Ybcc BY Yb AY aaX AY aa El lenguaje que genera L(G)={ anbncn / n>=1} |
||||
GRAMÁTICA DE TIPO 2 O LIBRES DE CONTEXTO: si cualquier producción tiene la forma; | ||||
A→a
, donde A ∈
V y a ∈
(V∪
T)* (el precedente de la implicación no posee
símbolos terminales o del alfabeto)
Un ejemplo de este tipo de gram�ica es G=({S}, {a, b}, P,S) donde las producciones son S →aSb, S→ε donde se genera el L(G)={aibi / i>=0} |
||||
GRAMÁTICA DE TIPO 3 O REGULARES: si toda la regla tiene la forma; | ||||
A→
uB o A→
u , donde A,B ∈
V y u ∈
T* (el consecuente de la implicación posee
una variable o símbolo no terminal precedida y seguida por un símbolo
terminal o del alfabeto)
Un ejemplo de este tipo3 de gramática es G=({S,B}, {a, b}, P,S) donde las producciones son S→ aS,S→ B B→ bB, B→ε donde se genera el L(G)={aibi /i,j>=0} |
||||
DEFINICIÓN | ||||
Un lenguaje se dice que es de un tipo i (i=0,1,2,3) si y solo si es generado por una gramática de tipo i. La clase o familia de lenguajes de tipo i se denota por Li. Se puede demostrar que L3 ⊆L2⊆ L1 ⊆ L0. | ||||
El conjunto
vacío es un lenguaje sobre cualquier alfabeto.