Teoria de la computacion

TEMA 3.2
ÁRBOLES DE DERIVACION

1. Define el concepto de árboles
Son conjuntos de nodos unidos entre si, por la relación padre (que parece dibujado por encima del nodo) y cero y mas hijos (dibujados por debajo) los árboles se conectan a los padres con sus hijos.

2. Por que se dice que todo nodo puede considerarse antepasado y descendiente de si mismo.
Por que el hijo deun hijo de un…nodo es un descendiente de ese nodo. El padre de un… nodo es un antepasado

3. Menciona los tipos de orden de los árboles
Preorden:
Cada padre precede a sus hermanos mayores y a los vértices del que es ancestro.
Entreorden:
En cada vértice interior se divide al conjunto de sus hijos en dos conjuntos [pic]y [pic]de manera que para cualquier pareja [pic]secumpla [pic]. En el entreorden se tiene que cada padre precede a sus hermanos mayores y a sus últimos hijos, pero sucede a sus hijos primeros.
Postorden:
Cada padre sucede a sus hermanos menores y a los vértices del que es ancestro.

4. Define brevemente como se compone un árbol de derivación
Hay un único nodo, la raiz, que no tiene padre, este nodo aparece en lo alto delárbol, los nodos sin hijos se llaman hojas, los nodos que no son hojas son nodos interiores.

5. Para que se utiliza el Árbol de Derivación
Se utiliza en los compiladores para representar la estructura sintáctica del programa fuente y facilita la traducción de código ejecutable.

6. Mencione las propiedades para la creación de un árbol de derivación
1. Cada nodo tiene unaetiqueta
2. La raíz tiene etiqueta S.
3. La etiqueta de los nodos que no son hojas debe estar en V, y las de las hojas en ∑U{ε}.
4. Si un nodo n tiene etiqueta A, y los nodos n1, . . . , nm son sus hijos (de izquierda a derecha), con etiquetas respectivamente A1, . . . ,Am, entonces A ( A1, . . . ,Am ε R.

7. Menciona que es un subárbol de derivación
Es un vérticeparticular del árbol junto con todos sus descendientes, las aristas conectadas a ellas. Se mide igual que un árbol de derivación.

8. Explica la equivalencia entre árbol de derivaciones y derivación
Una cadena Terminal esta en el lenguaje de una gramática y solo si es el resultado de al menos de una árbol de derivación. La existencia de derivaciones mas a la izquierda, derivaciones mas ala derecha y árboles de derivación son condiciones equivalentes, que definen exactamente las cadenas de lenguajes GIC.

8. Explica que es una forma sentencial
Se le conoce como una forma sentencial como cualquier paso de una derivación, es una cadena de variables o símbolo terminales.

9. Existe una cadena llamada resultado del árbol. ¿Cómo se obtiene?
Este obtiene a trabesdel proceso de observar las hojas de cualquier árbol de derivación y concatenarlas desde la izquierda.

TEMA 3.3
FORMAS NORMALES DE CHOMSKY

1. Fue el primer lingüística que propuso las gramáticas independientes como una forma de escribir lenguajes naturales
• N. Chomsky

2. Cuando podemos decir que esta gramática esta en la forma normal de Chomsky
• Cuando nocontiene símbolos inútil

3. Representa la forma normal de Chomsky
• A → B,C donde A,B,C son variable
• A → a donde A es una variable y a es un símbolo Terminal

4. En que forma se encuentra si tenemos dos variables o un símbolo Terminal en una ecuación
• En la forma normal de Chomsky

5. Menciona una aplicación de la forma normal de Chomsky
•Comprobar si una cadena pertenece a un lenguaje independiente del contexto

6. En que clasificación se encuentra el lenguaje de la forma normal de Chomsky
• Lenguaje libre de Contexto

7. Menciona un teorema de donde se tome como referencia de la forma normal de Chomsky
• Si G es una GIC que genera un lenguaje que contiene a menos una cadena distinta de ε, existe otra...