TEORIA DE LA COMPUTACION

UNIDAD 3

LENGUAJES LIBRES DE CONTEXTO Y AUTÓMATAS DE PILA

Veamos que todo lenguaje libre de contexto es reconocido por una autómata de pila.

  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.

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 detransiciones aplicadas para derivar la descripción final a partir de lainicial 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₁.

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 leyendade un árbol de derivación es la palabra obtenida al concatenarordenadamente, con cualquier orden de izquierda a derecha, lasetiquetas de sus hojas. Así pues, todo árbol de derivación tiene comoleyenda 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. 

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. La gramática G cuyas producciones son

es ambigua pues la palabra (ab)²a posee dos derivaciones diestras:

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

  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.

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

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

Primeramenteobservemos que podemos ``componer producciones'' de manera que tengamossiempre una gramática equivalente a la gramática dada.

(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.

(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 lagramática transformada. La demostración de la afirmación anterior esdirecta. Como mera ilustración, consideremos tan solo un ejemplo: Lagramá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:

   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

.
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_mpueden transformarse, siguiendo el lema  de ``Composición deproducciones'', en producciones equivalentes cuyos consecuentes seinician 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 de ``Composición deproducciones'', en producciones equivalentes cuyos consecuentes seinician 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.

Ejemplo:

Consideremos la gramática con símbolos variables

y producciones

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

lacual también tiene un consecuente que se inicia con un símbolo variableanterior 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

Conesto terminamos el paso 2. del procedimiento anterior. El conjuntoactual 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.:

Ejemplo ``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

Eneste momento, en nuestro conjunto actual de producciones 2., 3., 5., 7.y 9., ningún consecuente se inicia con alguna variable que anteceda ala variable en el antecedente de la producción correspondiente.

En el paso 3. del procedimiento para obtener formas normales de Greibach, hemos de sustituir la variable porel símbolo (, según la producción 2., toda vez que aparezca al iniciodel 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

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 yotra pila es su parte izquierda. Las transiciones de la máquina quedandeterminadas 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éntesisPara tener una cadena equilibrada, cada ``)'' en ella ha de ``empatar''con un correspondiente ``('' que lo anteceda. Para reconocer cadenasequilibradas 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..

UNIDAD 6                                          REDUCIBILIDAD

Problemas computables y no computables

Elidentificar los problemas que son computables y los que no lo son tieneun considerable interés, pues indica el alcance y los límites de lacomputabilidad, y así demuestra los límites teóricos de losordenadores. Además de las cuestiones sobre algoritmos, se hanencontrado numerosos problemas menos "generales" que han resultado serno computables. La mayoría de las demostraciones de no computabilidadse basan en el método de la diagonal. Como ejemplos de estos problemaspodemos citar:

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

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

3.-Decibilidad de las teorías lógicas. El desarrollo de la teoría de lacomputabilidad ha ido íntimamente ligado al desarrollo de la lógicamatemática. Esto ha sido así porque la decibilidad de los distintossistemas lógicos es una cuestión fundamental. Es bastante fácil ver queel cálculo proposicional es decidible. Church y Turing demostraron en1936 que el cálculo de predicados no era decidible. Por otro lado, paracada una de las distintas teorías se ha ido estudiando su posibledecibilidad. Como ejemplo más ilustrativo, Tarski demostró que lateoría de los números reales era decidible.

Porotro lado, son muchos los problemas interesantes que se han demostradocomputables. Todas las funciones construidas por recursividad primitivao minimalización a partir de funciones calculables resultan sercalculables como consecuencia de los trabajos de Church y Turing. Peroademás, otras funciones más complejamente definidas también soncomputables, siendo el resultado más significativo en relación con estacuestión el dado por el siguiente teorema:

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

Esteteorema recibe su nombre porque podemos definir una función medianteuna ecuación recursiva más general que la permitida por la recursividadprimitiva, a saber

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

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

Amenudo se utiliza la técnica de reducir un problema a otro paracomprobar si tiene o no solución efectiva. La estratégia en el caso dela respuesta negativa es la siguiente, si se reduce de forma efectivaun problema sin solución efectiva a otro problema (mediante una funcióncalculable), entonces este nuevo problema tampoco tendrá soluciónefectiva. La razón es muy simple, si tuviese solución efectiva,componiendo el algoritmo solución con el algoritmo de transformaciónobtendríamos una solución para el problema efectivamente irresoluble.En sentido inverso, si se reduce un problema a otro para el que seconoce una solución efectiva, entonces componiendo se obtiene unasolución para el primer problema. Esta técnica es muy útil y se utilizaa menudo. Por otro lado, esta mísma técnica es muy empleada en el campode la complejidad algorítmica. Para asegurarse de que un problema estáen una clase de complejidad, basta reducir el problema a otro de dichaclase sin más que asegurarse que la reducción se realiza en lacorrespondiente 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.

 TECNOLOGICO SUPERIOR DE SAN ANDRES TUXTLA

TEORIA DE LA COMPUTACION

ALUMNO: OSCAR RAFAEL TOM BAXIN

PROFESOR: ROGELIO ENRIQUE TELONA TORRES

ING.SIST.COMP. 404-B

JUNIO 2006

Escrito por tomba el 09/06/2006 05:19 | Comentarios (13)