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 de Greibach. 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

(La implicación `` '' se demuestra mediante inducción en el número de producciones utilizadas en una derivación siniestra de . El recíproco `` '' se demuestra mediante inducción en el número de transiciones aplicadas para derivar la descripción final a partir de la inicial en .) Ahora bien, si L contuviera a la palabra vacía , entonces, anulemos a todas las producciones- , o anulables, en una gramática que genere a y apliquemos lo anterior para encontrar un autómata de pila que reconozca a G₁. Ampliemos, finalmente, a añadiendo la transición .

ARBOLES Y GRAMATICAS

Sea G=(V,T,P,s₀) 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 el alfabeto 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 v₀ y es la palabra formada por las etiquetas de los hijos de v₀ entonces es una producción en P.

Un árbol gramatical es de derivación si su raiz está etiquetada con el símbolo inicial s₀ y todas sus hojas tienen etiquetas terminales o vací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 únicamente de 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(ba²)²=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,s₀) se dice ser ambigua si alguna palabra de su lenguaje, posee dos derivaciones diestras. Ejemplos. 1. La gramática G cuyas producciones son es ambigua pues la palabra (ab)²a posee dos derivaciones diestras:

2. Si para la gramática G=(V,T,P,s₀) 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 en V 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 contexto G'=(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 una sucesión de producciones de la forma siguiente: A cada símbolo terminal que aparezca en la palabra le asociamos una variable nueva X_a 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 producciones

FORMA NORMAL DE GREIBACH

Una gramática libre de contexto G=(V,T,P,S) se dice estar en forma normal de Greibach si sus producciones son de la forma

Veremos que la construcción de formas normales de Greibach equivalentes a gramáticas dadas es procedimental. Para cualquier gramática libre de contexto G, definamos, para cada variable , a los conjuntos siguientes:

Primeramente observemos que podemos ``componer producciones'' de manera que tengamos siempre una gramática equivalente a la gramática dada.

Lema 3.1 (Composición de producciones)   Si es una producción en G y las producciones en P(Y) pueden escribirse como entonces al sustituir por las producciones , obtenemos una gramática equivalente a G.

En efecto, en toda derivación terminal que aplique en un momento la producción , necesariamente se ha de aplicar una producción en P(Y) para suprimir el símbolo Y.

Lema 3.2 (Transformación de producciones ``reflexivas'')   Para cada variable enumeremos Q(X) y R(X) como

Sea Z una variable que no ocurra en V. Sea la gramática que se obtiene al sustituir el conjunto de producciones P(X) por las producciones

En efecto, toda derivación siniestra, en la gramática original, de una palabra en L(G) ha de determinar una derivación diestra de la misma palabra en la gramática transformada. La demostración de la afirmación anterior es directa. Como mera ilustración, consideremos tan solo un ejemplo: La gramática con producciones genera al lenguaje consistente de las palabras de la forma b(ab)^*. De acuerdo con la construcción anterior, como y , obtenemos la gramática

Presentemos sendas derivaciones, siniestra en la gramática original y diestra en la transformada, para la palabra bababab:

Veamos ahora el resultado principal de esta sección:

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 contexto G^*=(V^*,T,P^*,S^*) en forma normal de Greibach.

Sea pues G=(V,T,P,S) una gramática libre de contexto que no genere a . La transformación a una forma normal de Greibach la hacemos gradualmente mediante los pasos siguientes:

1.

Sea G'=(V',T,P',S') la forma normal de Chomsky de G.

2.

Modificaremos a las producciones en P' para tenerlas tales que toda producción, cuyo consecuente se inicie con una variable, ha de ser de la forma con j>i, para un cierto orden en el conjunto de variables actuales, digamos . Para esto apliquemos el procedimiento cuyo seudocódigo.

Por lo visto  la gramática G'' así obtenida es equivalente a G.

3

Ahora, hecha la transformación anterior, se tiene que

·        la última variable X_m sólo puede ser antecedente de producciones cuyos consecuentes se inician con símbolos terminales,

·        las producciones en P(X_m-1) cuyos consecuentes se inician con X_m pueden transformarse, siguiendo el lema 6.3.1 de ``Composición de producciones'', en producciones equivalentes cuyos consecuentes se inician con símbolos terminales,

·        de manera sucesiva para i=m-2 hasta i=1 las producciones en P(X_i) cuyos consecuentes se inician con algún X_j, con j>i, pueden transformarse, siguiendo el lema 6.3.1 de ``Composición de producciones'', en producciones equivalentes cuyos consecuentes se inician con símbolos terminales.

Con todas estas transformaciones la gramática resultante G^*=(V^*,T,P^*,S^*) es, en efecto, equivalente a G y está en forma normal de Greibach.

Consideremos la gramática con símbolos variables y producciones

la cual ya está en forma normal de Chomsky. Transformémosla de acuerdo con el procedimiento anterior. Observemos que las dos primeras producciones ya tienen el tipo de las buscadas en el paso 2. del procedimiento anterior. La tercera tiene un consecuente que se inicia con un símbolo variable anterior al de su propio antecedente. Compongamos pues la producción 3. con la 1. Obtenemos

la cual también tiene un consecuente que se inicia con un símbolo variable anterior al de su propio antecedente. Compongamos pues la producción 4. con la 2. Obtenemos

la cual es del tipo ``reflexivo''. Para transformarla, introduzcamos una nueva variable Y₃. Obtenemos
Con esto terminamos el paso 2. del procedimiento anterior. El conjunto actual de producciones consta de las producciones 1., 2., 6. y 7. Pasemos pues al paso 3. del procedimiento. Sustituyendo 6. en 2. obtenemos
Sustituyendo 8. en 1. obtenemos
Sustituyendo 9. en 7. obtenemos 10 nuevas producciones

En resumen, la gramática equivalente, en forma normal de Greibach, tiene como conjunto de variables a y sus producciones son la 6., 8., 9. y 10.:

 ``Cadenas equilibradas de paréntesis'':

Consideremos la gramática que genera a las cadenas equilibradas de paréntesis (CEP). La forma normal de Chomsky de la gramática dada es
Consideremos el siguiente orden de las variables: . La producción 1. es ``reflexiva''. Introduzcamos una nueva variable, X₁. Al hacer la transformación pertinente, obtenemos:
La producción 4. tiene un consecuente que se inicia con una variable anterior a su antecedente. Al componer 4. con 5. obtenemos
La producción 6. tiene un consecuente que se inicia con una variable anterior a su antecedente. Al componer 6. con 5. obtenemos
Al componer 8. con 2. obtenemos
En este momento, en nuestro conjunto actual de producciones 2., 3., 5., 7. y 9., ningún consecuente se inicia con alguna variable que anteceda a la variable en el antecedente de la producción correspondiente.

En el paso . del procedimiento para obtener formas normales de Greibach, hemos de sustituir la variable por el símbolo (, según la producción 2., toda vez que aparezca al inicio del consecuente de alguna producción. Obtenemos así la gramática:

Y esta gramática ya queda en forma normal de Greibach. Observemos que la variable es irrelevante. De hecho si hacemos la sustitución del otro símbolo obtenemos la gramática equivalente

que también está en forma normal de Greibach.

UNIDAD 4

MÁQUINAS DE TURING

Estas son autómatas finitas con dos pilas que tienen un tope común. O equivalentemente, son autómatas que poseen una memoria dada por una cinta la cual es un almacenamiento lineal, infinito a ambos lados, con acceso a cualquier localidad en ella. El tope común es la casilla leída (``scanned cell''), una pila es la parte de la cinta a la derecha de la casilla leída y otra pila es su parte izquierda. Las transiciones de la máquina quedan determinadas por una función , donde . Esta vez, la relación se interpreta como sigue: ``Si se está en el estado q y se lee el símbolo a entonces se escribe b, se pasa a p y se va a examinar la casilla al lado de la leída''. De hecho, la relación puede escribirse como , y por esto, decimos que una máquina de Turing queda especificada por su lista de quíntuplas. O, abusando aún más del lenguaje, que una lista de quíntuplas es el programa correspondiente a una máquina de Turing.

Ejemplo: Cadenas equilibradas de paréntesis Para tener una cadena equilibrada, cada ``)'' en ella ha de ``empatar'' con un correspondiente ``('' que lo anteceda. Para reconocer cadenas equilibradas procederemos como sigue:

• Cada ``('' ya empatado se marcará como ya revisado por una A y cada ``)'' se marcará por una B.
• Inicialmente, se busca el primer ``)'', yendo de izquierda a derecha.
• Por cada ``)'',
• se marca con B,
• se busca hacia la izquierda el primer ``('' que lo empate,
• si no se encontrare tal ``('' la cadena está desequilibrada. En otro caso, el ``('' se marca con A y se repite este ciclo.
• Si quedaren ``('' no empatados, la cadena está desequilibrada. En otro caso se tiene equilibrio y se termina el proceso.

El procedimiento queda descrito por la lista de quíntuplas mostrada en la tabla (5).

Los cuatro estados de la máquina tienen una interpretación evidente:

Como mero ejemplo, en la tabla  mostramos la computación correspondiente a una cadena dada. En cada instante, la casilla leída es la adyacente a la derecha del estado actual, el cual se escribe en negritas.

REDUCIBILIDAD

Funciones  computables y no computables

El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se han encontrado numerosos problemas menos "generales" que han resultado ser no computables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal. Como ejemplos de estos problemas podemos citar:

1.- El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuesta por elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchos años se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fué encontrada por Novikov en 1955 y por Boone en 1957. En el algebra moderna hay abundantes ejemplos de interesantes problemas no computables; una gran cantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra para grupos.

2.- Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o no solución. Y. Matiyasevich demostró en 1970 que este problema no tiene solución.

3.- Decibilidad de las teorías lógicas. El desarrollo de la teoría de la computabilidad ha ido íntimamente ligado al desarrollo de la lógica matemática. Esto ha sido así porque la decibilidad de los distintos sistemas lógicos es una cuestión fundamental. Es bastante fácil ver que el cálculo proposicional es decidible. Church y Turing demostraron en 1936 que el cálculo de predicados no era decidible. Por otro lado, para cada una de las distintas teorías se ha ido estudiando su posible decibilidad. Como ejemplo más ilustrativo, Tarski demostró que la teoría de los números reales era decidible.

Por otro lado, son muchos los problemas interesantes que se han demostrado computables. Todas las funciones construidas por recursividad primitiva o minimalización a partir de funciones calculables resultan ser calculables como consecuencia de los trabajos de Church y Turing. Pero además, otras funciones más complejamente definidas también son computables, siendo el resultado más significativo en relación con esta cuestión el dado por el siguiente teorema:

Primer teorema de Recursión. Todo operador entre funciones calculables que sea recursivo (esto es que se defina la imagen de f mediante una función calculable en términos de una parte finita de f), tiene una función parcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es una extension de esa función.

Este teorema recibe su nombre porque podemos definir una función mediante una ecuación recursiva más general que la permitida por la recursividad primitiva, a saber

donde es un operador recursivo. El primer teorema de recursión nos dice que esta definición es posible; hay una función recursiva que satisface esta ecuación. Como en matemáticas se requiere que la definición sea unívoca, se dice que dicha ecuación define el menor punto fijo del operador . Así, y de acuerdo al primer teorema de recursión, la clase de las funciones calculables es cerrada bajo una muy general forma de definición por recursión.

Como ejemplo más interesante de aplicación de este tipo de recursión tenemos la función de Ackermann :

A menudo se utiliza la técnica de reducir un problema a otro para comprobar si tiene o no solución efectiva. La estratégia en el caso de la respuesta negativa es la siguiente, si se reduce de forma efectiva un problema sin solución efectiva a otro problema (mediante una función calculable), entonces este nuevo problema tampoco tendrá solución efectiva. La razón es muy simple, si tuviese solución efectiva, componiendo el algoritmo solución con el algoritmo de transformación obtendríamos una solución para el problema efectivamente irresoluble. En sentido inverso, si se reduce un problema a otro para el que se conoce una solución efectiva, entonces componiendo se obtiene una solución para el primer problema. Esta técnica es muy útil y se utiliza a menudo. Por otro lado, esta mísma técnica es muy empleada en el campo de la complejidad algorítmica. Para asegurarse de que un problema está en una clase de complejidad, basta reducir el problema a otro de dicha clase sin más que asegurarse que la reducción se realiza en la correspondiente clase de complejidad.

Lenguajes aceptables y decidibles

- Lenguaje decidible: es aquel lenguaje L para el cual existe una máquina de Turing que

puede aceptar cualquier cadena w∈L y rechazar cualquier cadena w∉L.

- Lenguaje aceptable: es aquel lenguaje L para el cual no existe ninguna máquina de

Turing que puede aceptar cualquier cadena w∈L y rechazar cualquier cadena w∉L.

- Lenguajes recursivamente enumerables: lenguajes estructurados por frases.

- Lenguajes recursivos: lenguajes decidibles por una máquina de Turing.

INSTITUTO TECNOLOGICO SUPERIOR DE SAN ANDRES TUXTLA

INGENIERIA EN SISTEMAS COMPUTACIONALES

4 SEMESTRE  404-B

TEORIA DE LA COMPUTACION

APUNTES DE TEORIA DE LA COMPUTACION

ALUMNO:  SIXTECO PALAYOT ALBERTO

SAN ANDRES TUXTLA, VER.

Escrito por asixteco el 10/06/2006 01:14 | Comentarios (25)