Page 77 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

77

 El lenguaje generado por una gramática es el conjunto de cadenas de terminales obtenidas
a partir de derivaciones válidas usando las reglas de la gramática.
 Puede haber derivaciones conocidas como: “derivaciones por la derecha” o “derivaciones
por la izquierda”. Las derivaciones por la derecha son aquellas en donde se deriva primero
el no terminal situado más a la derecha. Esto es:

Ejemplo. Derivación por la derecha:

G= (VT, VN, S, P) VT= {A, B, BAS, BIG, BOSS}, S, P.
S A B C
B B BAS
B BIG C BOSS
C Λ
C C

Sí aplicamos la derivación por la derecha, primero reemplazamos el símbolo no terminal
C, quedando:

A B C  A B C

Luego viniendo por la derecha tomamos a él símbolo no terminal B y aplicamos la regla.

B BIG C BOSS o A BIG C BOSS C.

Volviendo a aplicar la reescritura, ahora sustituyendo al único no terminal que queda,
será:

A BIG C BOSS C

Si aplicaba la regla: C Λ, entonces hubiere quedado: A BIG BOSS C

Ejemplo. Derivación por la izquierda:

A B C

A B BAS C
A B BAS o A B BAS C

En fin, un lenguaje debe ser descrito a través de las propiedades que comparten las cadenas que
generan sus gramáticas.