Page 79 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

79

Reiterando la regla dice, que en el lado izquierdo de una producción pueden aparecer el símbolo
distinguido o un símbolo no terminal y en el lado derecho de una producción cualquier cadena de
símbolos terminales y/o no terminales de longitud mayor o igual que 1. La gramática puede
contener también la producción s → λ si el lenguaje que se quiere generar contiene la cadena
vacía.

Árboles de derivaciones y ambigüedad:

Un árbol de derivación es un árbol de análisis sintáctico en donde los nodos corresponden a los
nodos no terminales y terminales de la gramática y los hijos de cada nodo no terminal son los
símbolos que reemplazan a ese no terminal en la derivación (ningún símbolo terminal puede ser
nodo interior del árbol ni ningún símbolo no terminal puede ser hoja).
Ejemplo del árbol para la derivación anterior:

S

Z M N Z

A M A B N B

Z Z

Si se leen los nodos terminales de izquierda a derecha se obtiene la cadena anterior.

Cómo sería el árbol de la siguiente gramática:

S  X S X

S  Λ

Los teoremas que rigen estos conceptos, al igual que con las gramáticas regulares, autómatas
finitos, expresiones y lenguajes regulares son:

1- Para cualquier gramática G independiente del contexto existe un autómata de pila M tal
que L (M)=L (G).
2- Para cualquier autómata de pila M, existe una gramática G independiente del contexto
L(G)=L(M).