Arboles

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Lenguajes Libres de Contexto
Más allá de los Autómatas Finitos.

Universidad de Cantabria

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Esquema

1

Introducción

2

Árboles de Derivación

3

Un Algoritmo para la Vacuidad

Lenguajes IncontextualesIntroducción Árboles de Derivación Un Algoritmo para la Vacuidad

Introducción

Hemos visto que los lenguajes regulares son demasiado simples. Ahora tenemos que dar un paso más allá y estudiar los lenguajes libres de contexto.

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Introducción

Los lenguajes libres de contexto tienen una aplicación a loscompiladores, aunque existen otras aplicaciones como la compartición de información.

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Introducción

¿Por qué no ir un paso más allá? ¿Por qué no se estudian las gramáticas sensibles al contexto? Para gramáticas sensibles al contexto, el problema de decidir si el lenguaje que genera es vacío o notambién es un problema indecidible. En cuanto al Problema de Palabra para gramáticas sensibles al contexto, el problema es PSPACE–completo para ciertas subclases, con lo que se hace impracticable para su uso en la vida real.

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Introducción

¿Por qué no ir un paso más allá? ¿Por qué no se estudian lasgramáticas sensibles al contexto? Para gramáticas sensibles al contexto, el problema de decidir si el lenguaje que genera es vacío o no también es un problema indecidible. En cuanto al Problema de Palabra para gramáticas sensibles al contexto, el problema es PSPACE–completo para ciertas subclases, con lo que se hace impracticable para su uso en la vida real.

Lenguajes IncontextualesIntroducción Árboles de Derivación Un Algoritmo para la Vacuidad

Nota

PSPACE se refiere a la clase de problemas que pueden ser resueltos usando un número “eficiente” de espacio. PSPACE-Completo es la clase de problemas más difíciles de PSPACE.

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Definición

Definición (Gramáticas libres de contexto o deTipo 2) Llamaremos gramática libre de contexto a toda gramática G = (V , Σ, Q0 , P) tal que todas las producciones de P son del tipo siguiente: A → ω, donde A ∈ V y ω ∈ (Σ ∪ V )∗ . Un lenguaje libre de contexto es un lenguaje generado por una gramática libre de contexto.

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Definición

El sistema detransición asociado a una gramática libre de contexto es el mismo que asociamos a una gramática cualquiera. Usaremos el símbolo C G C para indicar que la configuración C es deducible de la configuración C mediante computaciones de G.

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Árboles de Derivación

Definición Llamamos formas sentenciales atodos los elementos ω de (V ∪ Σ)∗ . Llamaremos formas terminales a las formas sentenciales que sólo tienen símbolos en el alfabeto de símbolos terminales, es decir, a los elementos de Σ∗ .

Lenguajes Incontextuales

Introducción Árboles de Derivación Un Algoritmo para la Vacuidad

Árboles de Derivación
Definición (Árbol de Derivación) Sea G := (V , Σ, Q0 , P) una gramática libre de contexto,sea A ∈ V una variable. Diremos que un árbol TA := (V , E) etiquetado es un árbol de derivación asociado a G si verifica las propiedades siguientes: La raíz del árbol es un símbolo no terminal (i.e., una variable) y los otros nodos interiores están etiquetados con una variable y las hojas con un símbolo terminal o λ. Si un nodo está etiquetado con una variable X y sus descendientes (leídos de...