1.4.1.3 árboles sintácticos de derivación
Páginas: 3 (713 palabras)
Publicado: 22 de septiembre de 2015
Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje.
Un árbol es unconjunto de puntos, llamados nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de nodos y arcos debe satisfacer ciertas propiedades:
Hay unúnico nodo distinguido, llamado raíz (se dibuja en la parte superior) que no tiene arcos incidentes.
Todo nodo c excepto el nodo raíz está conectado con un arco a otro nodo k, llamado el padre de c (ces el hijo de k). El padre de un nodo, se dibuja por encima del nodo.
Todos los nodos están conectados al nodo raíz mediante un único camino.
Los nodos que no tienen hijos se denominan hojas, el restode los nodos se denominan nodos interiores.
Propiedades de un árbol de derivación.
Sea G = (N,T,S,P) una gramática libre de contexto, seauna variable. Diremos que un árbol TA = (N,E) etiquetado esun árbol de derivación asociado a G si verifica las propiedades siguientes:
· La raíz del árbol es un símbolo no terminal
· cada hoja corresponde a un símbolo terminal o λ.· cada nodo interior corresponde a un símbolo no terminal.
Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulouno de los símbolos de la cadena.
Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno delos símbolos de la cadena.
Si un nodo está etiquetado con una variable X y sus descendientes (leídos de izquierda a derecha) en el árbol son X1,…,Xk , entonces hay una producción X → X1…Xk en G.Sea G=(N,T,S,P) una GLC. Un árbol es un árbol de derivación para G si:
1. Todo vértice tiene una etiqueta tomada de
2. La etiqueta de la raíz es el símbolo inicial S
3. Los vértices...
Un árbol es unconjunto de puntos, llamados nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de nodos y arcos debe satisfacer ciertas propiedades:
Hay unúnico nodo distinguido, llamado raíz (se dibuja en la parte superior) que no tiene arcos incidentes.
Todo nodo c excepto el nodo raíz está conectado con un arco a otro nodo k, llamado el padre de c (ces el hijo de k). El padre de un nodo, se dibuja por encima del nodo.
Todos los nodos están conectados al nodo raíz mediante un único camino.
Los nodos que no tienen hijos se denominan hojas, el restode los nodos se denominan nodos interiores.
Propiedades de un árbol de derivación.
Sea G = (N,T,S,P) una gramática libre de contexto, seauna variable. Diremos que un árbol TA = (N,E) etiquetado esun árbol de derivación asociado a G si verifica las propiedades siguientes:
· La raíz del árbol es un símbolo no terminal
· cada hoja corresponde a un símbolo terminal o λ.· cada nodo interior corresponde a un símbolo no terminal.
Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulouno de los símbolos de la cadena.
Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno delos símbolos de la cadena.
Si un nodo está etiquetado con una variable X y sus descendientes (leídos de izquierda a derecha) en el árbol son X1,…,Xk , entonces hay una producción X → X1…Xk en G.Sea G=(N,T,S,P) una GLC. Un árbol es un árbol de derivación para G si:
1. Todo vértice tiene una etiqueta tomada de
2. La etiqueta de la raíz es el símbolo inicial S
3. Los vértices...
Leer documento completo
Regístrate para leer el documento completo.