Gramaticas GLC

Teor´a de Aut´ matas y Lenguajes Formales
ı
o
Bolet´n de Autoevaluaci´ n 5: ¿C´ mo se simplifica una Gram´ tica de Contexto Libre?.
ı
o
o
a

1.

Objetivos.

El objetivo de este bolet´n es ilustrar c´ mo proceder para simplificar gram´ ticas de contexto libre
ı
o
a
y, adem´ s, proporcionar la soluci´ n a alguno de los problemas propuestos en el bolet´n para que pod´ is
a
o
ı
acomprobar si hab´ is aplicado bien este m´ todo.
e
e

2.

Idea Principal.

Una gram´ tica nos proporciona un conjunto de producciones que nos permitir´ n obtener cadenas de
a
a
un determinado lenguaje. En este juego hay pocas reglas: una producci´ n nos indica c´ mo substituir una
o
o
serie de s´mbolos auxiliares por otra cadena de s´mbolos; se empieza siempre por un s´mbolo auxiliarı
ı
ı
´
especial, el s´mbolo S, start, y el objetivo es formar cadenas formadas unicamente por s´mbolos terminaı
ı
les esto es, s´mbolos del alfabeto sobre el que construimos el lenguaje. Al substituir no hay cota sobre el
ı
n´ mero de veces que se aplica una producci´ n y tampoco hay reglas que tengan una “preferencia” sobre
u
o
otras.
Al dise˜ ar la gram´ tica nuestra principalpreocupaci´ n es asegurar que se producen todas las cadenas.
n
a
o
De hecho, puede ocurrir que en el proceso de dise˜ o se introduzcan producciones que no facilitan la
n
obtenci´ n de cadenas o que introducen pasos innecesarios en el proceso de derivaci´ n.
o
o
El objetivo al simplificar una gram´ tica de contexto libre es obtener una gram´ tica equivalente, pero
a
a
´
en la que seasegura que cada derivaci´ n es util, y que no obliga a aplicar ning´ n paso innecesario.
o
u

3.

Pasos para simplificar una Gram´ tica de Contexto Libre.
a

Cualquier lenguaje de contexto libre, L, puede ser generado por medio de una GCL, G, que cumpla
las siguientes condiciones:
1.

Cada s´mbolo (terminal o auxiliar) de G se emplea en la derivaci´ n de alguna cadena de L.
ı
o

2.Si λ ∈ L entonces en el conjunto de producciones de G no existen producciones vac´as, es decir,
ı
producciones de la forma A → λ.

3.

En el conjunto de producciones de G no existen producciones unitarias, es decir, producciones de
la forma A → B donde A, B ∈ ΣA .

Si se obtiene una gram´ tica que cumpla estas tres condiciones se puede asegurar que en cada deria
vaci´ n que se realiza seintroduce informaci´ n relevante. ¿C´ mo se puede asegurar que son ciertas en
o
o
o
nuestra gram´ tica cada una de estas tres condiciones?
a
1

1.

Podemos asegurar que “cada s´mbolo (terminal o auxiliar) de G se emplea en la derivaci´ n de
ı
o
´
alguna cadena de L” si eliminamos los s´mbolos inutiles.
ı

2.

Podemos asegurar que “si λ ∈ L entonces en el conjunto deproducciones de G no existen producciones de la forma A → λ” si eliminamos las producciones vac´as.
ı

3.

Podemos asegurar que “en el conjunto de producciones de G no existen producciones unitarias”
si eliminamos las producciones unitarias.

Estos son los tres pasos que debemos seguir para asegurar que la gram´ tica est´ simplificada. A
a
a
continuaci´ n se desarrolla cada uno de ellos.
o

3.1.Procedimiento.

Para ilustrar el procedimiento se simplificar´ la gram´ tica G = {ΣA , ΣT , S, P }, en la que ΣA =
a
a
{S, A, B, C, D, E, F, G}, ΣT = {a, b, c} y el conjunto de producciones, P , es el siguiente:
S → Aab | B | CSa | b
A → aA | Cb | a | aBAE
B → bB | aBC | F | λ
C → CG | DC
D → aCb | a
E → aaE | bB
F → aF | ab
G→F

3.1.1.

´
Eliminaci´ n de s´mbolos inutiles.
oı

Hay que dividirlo en dos pasos y, adem´ s, el orden en que se realizan es significativo. Primero hay
a
que eliminar los s´mbolos no derivables y, despu´ s, los s´mbolos no alcanzables.
ı
e
ı

Eliminar los s´mbolos no derivables. Un s´mbolo auxiliar que nunca se podr´ substituir por un terı
ı
a
minal (o una cadena de terminales) es un s´mbolo no derivable. Y se puede eliminar de...