Reducibilidad

TEORIA DE LA COMPUTACION


LENGUAJES LIBRES DE CONTEXTO

Para cualquier lenguaje libre de contexto L existe un autómata de pila que reconoce al lenguaje, i.e.: libre de contexto y sea G una gramática libre de contexto que lo genere. Supongamos por un momento que la palabra vacía no pertenezca al lenguaje L. Podemos pues suponer que la gramática G=(V,T,P,S) está en forma normal deGreibach. Sea donde

La función del autómata definido es la de simular derivaciones siniestras, en la gramática G, de palabras en el lenguaje L. De hecho, se puede demostrar que se cumple la equivalencia


ARBOLES Y GRAMATICAS
Sea G=(V,T,P,s0) una gramática libre de contexto. Un árbol gramatical en G es un árbol ordenado tal que
• los vértices de están etiquetados con etiquetas en elalfabeto de la gramática o con la etiqueta vacía, , y
• cada vértice interior corresponde a una producción en G, es decir, si A es la etiqueta del vértice interior v0 y es la palabra formada por las etiquetas de los hijos de v0 entonces es una producción en P.
Un árbol gramatical es de derivación si su raiz está etiquetada con el símbolo inicial s0 y todas sus hojas tienen etiquetas terminales ovacía. La leyenda de un árbol de derivación es la palabra obtenida al concatenar ordenadamente, con cualquier orden de izquierda a derecha, las etiquetas de sus hojas. Así pues, todo árbol de derivación tiene como leyenda una palabra en L(G). Recíprocamente, para cada palabra en L(G) existe un árbol de derivación cuya leyenda coincide con . Si y , donde es una producción en P y consiste únicamentede símbolos terminales, decimos que se sigue de por la aplicación diestra de una producción. Una derivación es diestra si todas las aplicaciones de producciones hechas son diestras. Las derivaciones siniestras se definen simétricamente. Ejemplo. Consideremos las siguientes producciones:

Sendas derivaciones siniestra y diestra de la palabra a(ba2)2=abaabaa son las siguientes:En el lenguaje L(G) generado por esta gramática se encuentran incluidos los siguientes lenguajes:
• . De hecho, .
• . De hecho, , con y x como antes.
• , donde y

Para concluir esta sección presentaremos las nociones de ambigüedad en gramáticas. Una gramática libre de contexto G=(V,T,P,s0) se dice ser ambigua si alguna palabra de su lenguaje, posee dosderivaciones diestras. Ejemplos. 1. La gramática G cuyas producciones son es ambigua pues la palabra (ab)2a posee dos derivaciones diestras:

2. Si para la gramática G=(V,T,P,s0) incluimos una copia V' del conjunto de variables no-iniciales más copias de las producciones de P con símbolos en S' entonces la nueva gramática es ambigua pues cada derivación diestra puede derivarse considerando símbolos enV o en su contraparte V'.



FORMA NORMAL DE CHOMSKY
Una gramática libre de contexto G=(V,T,P,S) se dice estar en forma normal de Chomsky si sus producciones son de cualquiera de las dos formas
• con , o bien
• con y .
Proposición 3.1 Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía se puede transformar en una gramática libre de contextoG'=(V',T,P',S') en forma normal de Chomsky.
En efecto, dada una gramática G, apliquemos el último procedimiento de la sección anterior para transformar a G en una gramática G'' sin variables inútiles ni producciones vacías ni producciones unitarias equivalente a G. A las producciones que quedasen de la forma con y las dejamos sin cambio alguno. A cada producción de la forma , con y , la transformamos en unasucesión de producciones de la forma siguiente: A cada símbolo terminal que aparezca en la palabra le asociamos una variable nueva Xa e incorporamos la producción . Así pues las producciones que no sean de la forma con X variable y a terminal, han de ser de la forma , con todos variables. Para cada una de estas últimas producciones introducimos k-2 nuevas variables e incorporamos la sucesión de...