Principios fundamentales de autómatas y gramáticas

Trabajo profesional que para obtener el titulo de

Ingeniero en Sistemas Computacionales

2. Autómatas finitos y lenguajes regulares
3. Autómatas de pila y lenguajes libres de contexto
4. Autómatas lineales y lenguajes sensibles al contexto
5. Máquinas de turing y lenguajes recursivos enumerables
6. Aplicaciones a lenguajes
7. Bibliografía
8. Glosario
9. Anexos

CAPÍTULO I

INTRODUCCIÓN

Objetivo:

El alumno recordará y aplicará las operaciones básicas de conjuntos así como definirá los elementos de un lenguaje. Además conocerá la clasificación de las gramáticas.

1.1. CONJUNTOS.

Un conjunto es una colección de objetos llamados elementos del conjunto. Si A es un conjunto y a es un elemento de A utilizaremos la notación a Î A (se lee "a es un elemento de A"). Se usa la notación bÏ A cuando b no es un elemento de A.

Si A contiene exactamente los elementos a1, a2, …, an, lo indicamos escribiendo A= {a1, a2, …, an}.

Un conjunto sólo se caracteriza por sus elementos y no por el orden en el cual se listan.

Los conjunto A y B son iguales si contienen los mismos elementos. Por lo tanto si, A={1,2,3} y B={2,1,3} se puede escribir que A = B.

Algunas veces es conveniente describir el contenido de un conjunto en términos de una propiedad que sea característica de todos los elementos del conjunto. Sea P(x) una proposición sobre x. La notación {x| P(x)}, que se interpreta como "el conjunto de todas las x tales que P(x)", denota el conjunto de todos los x para los cuales P(x) es una proposición verdadera. (Todas las x tienen la propiedad P).

1.2. OPERACIONES CON CONJUNTOS.

Las operaciones habituales que se definen sobre los conjuntos son:

El conjunto Æ llamado conjunto vacío o nulo, no tiene elementos. El conjunto vacío es un subconjunto de todos los conjuntos.

La unión de conjuntos A y B se denota por A È B y es un conjunto formado por los elementos que aparecen en A, en B o en ambos.

Por lo tanto A È B ={x|xÎ A ó x Î B}.

Por ejemplo, si A={1, 2, 3} y B= {a, b}, entonces A È B={1, 2, 3, a, b}.

La intersección de A y B es el conjunto de todos los elementos que aparecen simultáneamente en A y también en B.

Por lo tanto A Ç B ={x|xÎ A y x Î B}.

Por ejemplo, si A={1, 4, 5, 7} y B= {2, 4, 7, 8}, entonces A Ç B={4, 7}.

El complemento relativo si A y B son dos conjuntos cualesquiera, el complemento de B con respecto a A es el conjunto: A–B={x|xÎ A y xÏ B}.

Por lo tanto, A–B esta compuesto por todos los elementos de A que no están también en B. Por ejemplo, si A={0, 2, 4, 6, 8, 10} y B={0,1, 2, 3, 4}, entonces A–B={6, 8, 10}, mientras que B–A={1, 3}.

2A , el conjunto potencia de A, es el conjunto formado por todos los subconjuntos de A. Por ejemplo, sea A={a, b, c} . Entonces 2A ={Æ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Dados dos conjuntos A y B, su producto cartesiano, AxB, es el conjunto de todos los pares ordenados de los que el primer elemento proviene de A y el segundo de B. Así que, AxB ={(a, b)|aÎ A y bÎ B}. Por ejemplo, sí A={1,2,3} y B={5,6} entonces: AxB ={(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)}.

Si A y B son conjuntos y todos los elementos de A son también elementos de B, se escribe A Í B y se dice que A es un subconjunto de B. Por ejemplo A={1,2,3} y B={0,1,2,3,4,5} , se tiene A Í B. Por otro lado, B no es un subconjunto de A, porque los elementos 0, 4 y 5 de B no lo son de A.

La Inclusión cuando cualquier elemento de A que este en B, o cualquier elemento de B que este en A, ó que sean iguales. Por ejemplo si A={2, 4, 5, 7, 8} y B={2, 4}, entonces AÌ B={2, 4}.

La cardinalidad de un conjunto es el número de elementos de ese conjunto. Por ejemplo si A={a, b} entonces |A|=2. La cardinalidad del conjunto vacío es 0 porque no tiene ningún elemento.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Todos los conjuntos aquí tratados se consideran subconjuntos de un conjunto universal U. Los complementos pueden ser formados con respecto a este conjunto universal. Si A es un conjunto, entonces U- A es el conjunto de todos los elementos que no están en A. Conviene denotar tales complementos mediante A, de forma que U- A = A. Obsérvese que Æ =U y U = Æ .

1.3. ALFABETOS.

Un alfabeto es un conjunto no vacío y finito de símbolos. En el caso del alfabeto inglés, la colección finita es el conjunto de las letras del alfabeto junto con los símbolos que se usan para construir palabras en inglés (tales como el guión, el apóstrofe y otros por el estilo).

Cada símbolo de un alfabeto es una cadena sobre dicho alfabeto. La cadena vacía, la cual se denota por el símbolo e , es una palabra sobre cualquier alfabeto.

1.4. PROPIEDADES DE LAS CADENAS O "STRINGS".

Una cadena (ó palabra) es una secuencia finita de símbolos. Por ejemplo: a, b y c son símbolos y abcb es una cadena.

1.4.1. Cadena Vacía.

La cadena vacía, denotada por e es la cadena que consiste en cero símbolos. Por tanto, tiene longitud |e |=0.

1.4.2. Longitud.

Si w es una cadena sobre cualquier alfabeto, su longitud se denota como |w |. La longitud de w es el número de símbolos que tiene la cadena. Por ejemplo: abcb tiene longitud |w | =4.

1.4.3. Concatenación.

La concatenación de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas. Por ejemplo: si w= "banana" y z= "rama", la concatenación de w con z es la cadena "bananarama". La concatenación de las cadenas w y z se denota como wz ó w.z. La cadena vacía es la identidad para el operador de concatenación. Es decir, e w= we =w para cada cadena w.

1.4.4. Potencia de Cadenas.

La noción de potencia de una cadena sobre un alfabeto es dada por la notación wk que denota la concatenación de k copias de la cadena w.

Por tanto, si w=122 sobre el alfabeto S ={1, 2}, se tiene

w0 = e

w1 = 122

w2 = 122122

w3 = 122122122

1.4.5. Igualdad de Cadenas.

Si w y z son cadenas, se dice que w es igual a z, si tienen la misma longitud y los mismos símbolos en la misma posición. Se denota mediante w =z.

1.4.6. Prefijo.

Los prefijos de una cadena están formados por los primeros símbolos de ésta. Por ejemplo, la cadena 121 sus prefijos son: e , 1, 12 y 121, con lo que toda palabra puede considerarse prefijo de sí misma. Un prefijo de una cadena que no sea la misma cadena es un prefijo propio.

1.4.7. Sufijo.

Los sufijos de una cadena están formados por los últimos símbolos de está. Por ejemplo, la cadena abc sus prefijos son: e , c, bc y abc. Un sufijo de una cadena que no sea la misma cadena es un sufijo propio.

1.4.8. Subcadena.

Una cadena w es una subcadena o subpalabra de otra cadena z si existen las cadena x e y para las cuales z= xwy.

1.4.9. Transpuesta.

La inversa o transpuesta de una cadena w es la imagen refleja de w. Por ejemplo, si w = "able" entonces su inversa es "elba". Para denotar la inversa de w se usa wI.

1.5. REPRESENTACIÓN FINITA DEL LENGUAJE.

Un alfabeto es un conjunto finito de símbolos.

Un lenguaje (formal) es un conjunto de cadenas de símbolos tomados de algún alfabeto. El conjunto vacío, Æ y el conjunto formado por la cadena vacía {e } son lenguajes. Nótese que son diferentes: el último tiene un elemento, mientras que el primero no. El conjunto de Palíndromos (cadenas que se leen igual de izquierda a derecha y viceversa) sobre el alfabeto {0,1} es un lenguaje infinito. Algunos elementos de este lenguaje son e , 0, 1, 00, 11, 010 y 1101011.

Otro lenguaje es el conjunto de cadenas sobre un alfabeto fijo S . Denotamos a este lenguaje como S * llamado como la cerradura de Kleene o cerradura de estrella de un lenguaje. Las cadenas de la cerradura de Kleene se forman al realizar cero o más concatenaciones de las cadenas del alfabeto, mientras que la cerradura positiva se forma al realizar una o más concatenaciones. Por ejemplo si S ={a}, entonces tenemos que S 0= {e }, S 1={a}, S 2= {aa} y así sucesivamente. Por tanto S *= {e , a, aa, aaa,…}. Por otro lado, S += {a, aa, aaa,…}.

1.6. CLASIFICACIÓN DE LAS GRAMÁTICAS.

En 1959, Noam Chomsky clasificó las gramáticas en cuatro tipos de lenguajes y esta clasificación es conocida como la jerarquía de Chomsky, en la cual cada lenguaje es descrito por el tipo de gramática generado. Estos lenguajes sirven como base para la clasificación de lenguajes de programación. Los cuatro tipos son: lenguajes recursivamente enumerables, lenguajes sensibles al contesto, lenguajes libres de contexto y lenguajes regulares. Dichos lenguajes también se identifican como lenguajes de tipo o, 1, 2 y 3.

Existe una exacta correspondencia entre cada uno de estos tipos de lenguajes y particulares arqitecturas de máquinas en el sentido que por cada lenguaje de tipo T hay una arquitectura de máquina A que reconoce el lenguaje de tipo T y por cada arquitectura A hay un tipo T tal que todos los lenguajes reconocidos por A son de tipo T. La correspondencia entre lenguajes y arquitectura son mostrados en la siguiente tabla, la cual también indica el capítulo de donde se explican más a fondo, figura 1.1.

Figura 1.1. Los cuatro tipos de Gramáticas.

La relación entre los lenguajes es descrita a continuación:

Sobre un alfabeto dado, el conjunto de los lenguajes recursivamente enumerables contiene propiamente al conjunto de los lenguajes recursivos que contiene propiamente al conjunto de los lenguajes sensibles al contexto que contiene propiamente al conjunto de lenguajes libres de contexto, que a su vez contiene propiamente a los lenguajes regulares.

EJERCICIOS.

* Ejercicio resuelto.

*1.1. Sean A y B dos lenguajes sobre S . Probar las siguientes afirmaciones:

a) A – B = A Ç B.

b) (A È B) = A Ç B.

a) A – B = A Ç B.

Un elemento x satisface

xÎ A – B Û xÎ A y xÏ B

Û xÎ A y x Î B

Û xÎ A Ç B

Por lo tanto A – B = A Ç B.

b) (A È B) = A Ç B.

Un elemento x satisface

xÎ A È B Û xÏ AÈ B

Û xÎ A y xÏ B

Û xÎ A y xÎ B

Û xÎ A Ç B

Por lo tanto (A È B) = A Ç B.

1.2. Probar o refutar las siguientes afirmaciones:

a) Si A È B = A È C, entonces B = C

b) Si A Ç B = A Ç C, entonces B = C

1.3. Demostrar las siguientes igualdades:

A È (B È C) = (A È B) È C.

A È (B Ç C) = (A È B) Ç (A È C).

*1.4. Si A={rojo, verde, azul}, B={verde, violeta} y C={rojo, amarillo, azul, verde}. Determine los elementos en (A Ç C) x (B – C).

A Ç C = {rojo, verde, azul}

B – C = {violeta}

(A Ç C) x (B – C) = {(rojo, violeta), (verde, violeta), (azul, violeta)}

*1.5. Demuestre la siguiente igualdad A – B = A – (B Ç A), utilizando los siguientes conjuntos: A={a, d, e. f, g} y B={d, g, h, j}

B Ç A = {d, g}

A – (B Ç A) = {a, e, f}

A – B = {a, e, f}

Por lo tanto A – B = A – (B Ç A)

1.6. Demuestre la siguiente igualdad (A – B) – C = (A – C) – (B – C) = A – (B È C), utilizando conjuntos a su libre albedrio.

*1.7. ¿De qué conjunto de símbolos se derivan las frases inglesas?

Las frases inglesas se derivan del alfabeto inglés, que esta formado por veintiseis símbolos.

*1.8. ¿Por qué el lenguaje vacío Æ no es el mismo que {e }?

Dado que el lenguaje es un conjunto de cadenas, se puede tener el lenguaje compuesto por ninguna cadena (el lenguaje vacío). Este no es el mismo lenguaje que el que consta de la cadena vacía {e }.

1.9. Obtener todos los prefijos y sufijos de la palabra w="bar" sobre el alfabeto inglés.

1.10. Sea A={la, mi} y B={calza, caballo, casa}. Obtener A.B, A.A y A.B.B.

1.11. ¿Bajo qué condiciones A*=A+?

*1.12. Probar que {e }*={e }={e }+.

Si S ={e }

Las cadenas de la cerradura de Kleene S *=S n donde n³ 0 entonces tenemos que S 0={e }, S 1={e }, S 2={e e } y así sucesivamente.

Por lo tanto S *= {e , e , e e , e e e , …}, sigue siendo {e }.

Por otro lado, la cerradura positiva S +=S n donde n³ 1, entonces tenemos S += {e , e e , e e e , …}, que sigue siendo {e }.

Por lo tanto {e }*={e }={e }+.

*1.13. En terminos de la cerradura de kleene y la cerradura positiva, describa que cadenas se obtienen a partir del siguiente lenguaje: 0(0*10*)+.

Conjunto de cadenas binarias que empiezan con 0 y que contienen al menos un 1.

1.14. En terminos de la cerradura de kleene y la concatenación de cadenas, describa los lenguajes que contengan los siguientes enunciados:

a) Cadenas sobre {0, 1} que empiecen con 01.

b) Cadenas que comiencen con 0, alternando entre 0 y 1.

AUTÓMATAS FINITOS Y

LENGUAJES REGULARES

Objetivo:

El alumno conocerá la fundamentación de los autómatas finitos, aprenderá a construir autómatas finitos determinísticos, autómatas no determinísticos y autómatas no determinísticos con movimiento e y relacionará dichos autómatas con expresiones regulares.

2.1. AUTÓMATAS FINITOS DETERMINÍSTICOS (DFA’S).

Las características de los autómatas finitos determinísticos son:

1. Un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto S .
2. Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado).
3. Un estado, por lo general denotado como q0 es el estado inicial, en el que el autómata comienza.
4. Algunos estados (tal vez ninguno) están designados como final o de aceptación.

Un autómata finito determinístico es una quinta tupla (Q, S , d , q0, F) donde:

Q es un conjunto finito de estados.

S un alfabeto de entrada finito.

q0 elemento de Q , el estado inicial.

FÍ Q el conjunto de estados finales o de aceptación.

d es la función d : Q x S ® Q que determina el único estado siguiente para el par (q1, s ) correspondiente al estado actual q1 y la entrada s .

Generalmente el término autómata finito determinístico se abrevia como DFA de sus siglas en inglés Deterministic Finite Automaton. Usaremos M = (Q, S , q0, F, d ) para indicar el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociadas con el DFA M.

Se puede construir un diagrama para que ayude a determinar los distintos miembros o cadenas del lenguaje. Tal diagrama tiene la forma de un grafo dirigido con información añadida, y se llama diagrama de transición. Los nodos del grafo corresponden a los estados del DFA y se usan para señalar, en ese momento, hasta qué lugar se analizó la cadena. Por lo general q0 es el estado inicial, marcando con una flecha (® ), el comienzo del autómata; algunos estados están designados como final o aceptación indicados por un doble círculo. Los símbolos del alfabeto son las etiquetas de los arcos del grafo. Si cuando ha sido tratada la cadena en su totalidad se termina en un estado de aceptación entonces la cadena es aceptada por el lenguaje. Si M es un AFD, entonces el lenguaje aceptado por M es L(M)={w Î S *½ w es aceptada por M}. Por tanto, L(M) es el conjunto de cadenas que hacen que M pase de su estado inicial a un estado de aceptación.

Ejemplo: El lenguaje que acepta el DFA esta formado por todas las cadenas sobre el alfabeto S = {a, b}, siempre y cuando terminen con a.

Figura 2.1.

Q = {q0, q1}, S = {a, b}, q0 = q0 , F = {q1} y d se define mediante la tabla de la figura 2.1.

Se puede utilizar también la siguiente lista para definir la función d

(q0, a) = q1(q0, b) = q0

(q1, a) = q1(q1 ,b) = q0

El diagrama de transición se muestra en la figura 2.2.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Consideremos otro ejemplo. El DFA M= {Q, S , q0, F, d } acepta el lenguaje L(M)={w Î {a, b}* que no contiene tres b’s consecutivas} y esta representada por:

Q={q0, q1, q2, q3}

S ={a, b}

q0=q0

F={q0, q1, q2}

y d dada por la tabla de la figura 2.3.

Figura 2.3.

El diagrama de transición correspondiente se muestra en la figura 2.4.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

2.2. AUTÓMATAS FINITOS NO DETERMINÍSTICOS (NFA’S).

Un autómata finito no determinístico es una quinta tupla ( Q, S , q0, d , F) en donde Q, S , q0 y F (estados, entradas, estado inicial y estados finales) poseen el mismo significado que para un DFA, pero en este caso d es una transformación de Q x S a 2Q. (Recuérdese que 2Q es el conjunto de potencias de Q, el conjunto de todos los subconjuntos de Q). Obsérvese que puesto que d es una relación para todo par (q, s ) compuesto por el estado actual y el símbolo de la entrada, d (q, s ), es una colección de cero o más estados [es decir, d (q, s )Í Q]. Esto indica que, para todo estado q1 se pueden tener cero o más alternativas a elegir como estado siguiente, todas para el mismo símbolo de entrada.

Generalmente el término autómata finito no determinístico se abrevia como NFA de sus siglas en inglés Nondeterministic Finite Automaton. Si M es un NFA, definiremos el lenguaje acepatdo por M por medio de L(M)={w ½ w es una cadena aceptada por M} donde una cadena w es aceptada por M, si M pasa de su estado inicial a su estado de aceptación o final al recorrer w (w es consumida en su totalidad).

Observe ahora el diagrama de transición de la figura 2.5

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

El NFA descrito anteriormente acepta el lenguaje formado por cualquier número (incluyendo el cero) de a’s, concatenadas a una "b" ó una "a" concatenada a cualquier numero (incluyendo el cero) de b’s . Se representa de la siguiente forma:

Q={q0, q1, q2, q3, q4}

F={q2, q3, q4}

q0=q0

S ={a, b}

Y d dada por la tabla de la figura 2.6.

Figura 2.6.

Obsérvese que en el contenido de las celdas de la tabla de transición de la figura 2.6 son conjuntos. El hecho de que existan celdas con Æ , indica que no existe ninguna transición desde el estado actual mediante la entrada correspondiente. Que para un par (estado actual, entrada) exista más de un posible estado siguiente indica que se puede elegir entre las distintas posibilidades. En el modelo no existe nada que determine la elección. Por esta razón, se dice que el comportamiento del autómata es no determinista.

Veamos otro ejemplo. Consideremos el NFA M={ Q, S , q0, F, d } que acepta el lenguaje formado por cadenas que tienen cero o más ocurrencias de "ab" ó "aba" y esta dado por:

Q={q0, q1, q2} S ={a, b}

q0=q0F={q0}

Figura 2.7.

Y d dada por la tabla de la figura 2.7. Este NFA tiene el correspondiente diagrama de transición que se muestra en la figura 2.8.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Figura 2.8.

2.3. AUTÓMATAS FINITOS NO DETERMINÍSTICOS CON MOVIMIENTO e (NFA- e ).

Un autómata finito no determinístico con movimiento e (entrada vacía) es como la quinta tupla ( Q, S , d , q0, F) con todos sus componentes igual que a un NFA, con excepción de d , la función de transición, que ahora transforma Q x (S È {e }) a 2Q; para incluir transiciones de un estado a otro que no dependan de ninguna entrada. Se puede añadir una columna en la tabla de d para colocar los pares de la forma (qi, e ). Cuando hay e -transiciones en un NFA es conveniente suponer que cada estado tiene una e -transición que cicla en ese estado.

Observe el ejemplo del diagrama de transición de la figura 2.9, que acepta el lenguaje consistente en cualquier número (incluyendo el cero) de 0’s seguidos por cualquier número de 1’s seguido, a su vez, por cualquier número de 2’s y cuya tabla de transición es mostrada por la figura 2.10.

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

Figura 2.9.

Figura 2.10.

Veamos otro ejemplo con el diagrama de transición de la figura 2.11 que acepta el lenguaje formado por cadenas que tienen cero o más ocurrencias de "ab" ó "aba".

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 La figura 2.11 tendría la tabla de transición de la figura 2.12

Figura 2.12.

2.4. EXPRESIONES REGULARES.

Los lenguajes aceptados por un autómata finito se describen con facilidad mediante expresiones simples llamadas expresiones regulares.

Sea S un alfabeto. La expresión regular sobre S y los conjuntos que denotan se definen de manera recursiva como sigue:

1. Æ es una expresión regular y denota al conjunto vacío.
1. e es una expresión regular y denota al conjunto {e }.
1. Para cada a Î S , a es una expresión regular y denota al conjunto {a}.
1. Si r y s son expresiones regulares que denotan a los lenguajes R y S.; respectivamente, entonces tenemos lo siguiente:

r+s es una expresión regular que denota a los conjuntos R È S.

(r) es una expresión regular que denota al conjunto R.

rs es una expresión regular que denota a los conjuntos RS.

r* es una expresión regular que denota al conjunto R*.

r+ es una expresión regular que denota al conjunto R+.

ri es una expresión regular que denota al conjunto Ri.

Ejemplo de Autómatas con sus expresiones regulares

El lenguaje del autómata de la figura 2.13. esta formado por cualquier cadena de 1’s, incluyendo e .

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.13. La expresión regular del autómata es: 1*

El lenguaje del autómata de la figura 2.14. esta formado por todas las cadenas de a’s de longitud par, incluyendo e .

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.14. La expresión regular del autómata es: (aa)*

El lenguaje del autómata de la figura 2.15. esta formado por cadenas de cero ó más a’s seguidas de cero ó más b’s.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.15. La expresión regular del autómata es: a*b*.

Existen muchas equivalencias con respecto a expresiones regulares basadas en las correspondientes igualdades de lenguajes. Por ejemplo sean r, s y t expresiones regulares sobre el mismo alfabeto S . Entonces:

1. r + s = s + r
2. (rs)t = r(st)
3. (r + s)t = rt + st
4. (r*)* = r*
5. r(s + t) = rs + rt

2.5. LENGUAJES REGULARES.

Los lenguajes regulares pueden ser usados en la construcción de analizadores léxicos – programas que analizan un texto y extraen los lexemas ( o unidades léxicas) que hay en el mismo -.

El conjunto de los lenguajes regulares sobre un alfabeto S esta formado por el lenguaje vacío, los lenguajes unitarios incluido {e } y todos los lenguajes obtenidos a partir de la concatenación, unión y cerradura de estrella de lenguajes.

Ejemplo de lenguajes regulares:

Cuando sea necesario distinguir entre una expresión regular r y el lenguaje denotado por la misma, usaremos L(r) para denotar el lenguaje. En cualquier caso, si se afirma que w Î r, ello equivale a decir que w Î (r). Si r y s son expresiones regulares sobre el mismo alfabeto y si L(r)= L(s), entonces se dice que r y s son equivalentes. En el caso de que r y s sean equivalentes se puede escribir r= s. También se puede usar rÍ s en el caso de que L(r) Í L(s).

2.6. FUNCIONES RECURSIVAS.

Una definición recursiva esta caracterizada por un proceso de tres pasos:

1. Declaración de los objetos básicos que pertenecen al lenguaje (caso base).
2. Otorgar las reglas para construir más objetos a partir de los existentes (caso recursivo).
3. Declarar que ningún otro objeto fuera de las dos reglas anteriores forman parte del lenguaje "Requisito de formalidad".

Ejemplo: Encontrar una definición recursiva para el lenguaje de todos los números enteros divisibles a través de 2, es decir, EVEN= {2, 4, 6, 8, …}.

1. 2 Î EVEN.
2. x Î EVEN entonces x+2 Î EVEN.
3. Ningún otro número que no sea obtenido por la regla 1 y la regla 2 Î EVEN.

Para explicar está definición se recorre la función recursiva, para demostrar que el número 14 Î EVEN:

Por la regla 1 2Î EVEN

Por la regla 2 2+2=4 Î EVEN

Por la regla 2 4+2=6 Î EVEN

Por la regla 2 6+2=8 Î EVEN

Por la regla 2 8+2=10 Î EVEN

Por la regla 2 10+2=12 Î EVEN

Por la regla 2 12+2=14 Î EVEN

El anterior recorrido queda más claro mediante figura 2.16.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.16. Recorrido de la función recursiva, para demostrar que el número 14 Î EVEN.

Sin embargo, la anterior definición recursiva no es la única, pueden adaptarse otras, por ejemplo:

1. 2 Î EVEN.
2. X,Y Î EVEN entonces X+Y Î EVEN.
3. Ningún otro número Î EVEN.

El recorrido de la función recursiva para el número 14 quedaría de la siguiente forma:

Por la regla 1 2Î EVEN

Por la regla 2 x=2, y=2 entonces 2+2=4 Î EVEN

Por la regla 2 x=2, y=4 entonces 2+4=6 Î EVEN

Por la regla 2 x=4, y=4 entonces 4+4=8 Î EVEN

Por la regla 2 x=6, y=8 entonces 6+8=14 Î EVEN

Esta segunda definición recursiva es mejor que la primera porque se obtiene el resultado en un menor número de pasos como se observa en la figura 2.17.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.17. Recorrido de la segunda función recursiva, para demostrar que el número 14 Î EVEN.

La definición recursiva que se obtenga dependerá de dos casos:

1. Que tan fácil de entender es la definición recursiva.
2. Los tipos de teoremas que se desean demostrar.

2.7. PUMPING LEMMA O LEMA DE BOMBEO PARA LENGUAJES REGULARES.

Si L es un lenguaje finito, es regular y se podrá construir un autómata finito o una expresión regular para ellos de forma sencilla. También, si L es especificado ya sea por medio de un autómata finito o una expresión regular, la respuesta es obvia. Por desgracia, hay relativamente pocos lenguajes que sean regulares y, en el caso de un lenguaje infinito, la búsqueda exhaustiva de una expresión regular o un autómata finito puede resultar inútil. En este caso, se necesita obtener algunas propiedades que compartan todos los lenguajes regulares infinitos y que no estén presentes en los lenguajes regulares.

Supongamos que un lenguaje es regular y que, por tanto, es aceptado por un DFA M=(Q, S , q0, d , F), donde Q contiene n estados. Si L(M) es infinito, podremos encontrar cadenas cuya longitud sea mayor que n. Supongamos que w= a1, a2, …,an+1 es una de las cadenas de longitud n+1 que pertenecen a L(M).

Si tuviéramos

q1= d (q0, a1)

q2= d (q1, a2)

y así sucesivamente, obtendríamos los n+1 estados, q1, q2 ,…, qn+1. Puesto que Q contiene sólo n estados , los qi no serán todos distintos. En consecuencia, para algunos índices j y k, con 1£ j £ n+1, se obtendrá que qj= qk. Por lo tanto, tendremos un ciclo en el camino que parte de q0 hasta un estado de aceptación según se muestra en la figura 2.18.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.18.

Puesto que j< k, se tiene que la "parte central", es decir, aj+1…ak, tiene al menos longitud 1. Obsérvese además que la cadena w’= a1… aj ak+1…an+1 debe pertenecer también a L(M). Por esto, se puede dar vueltas en el ciclo tantas veces como se quiera, de forma que a1… aj (aj+1…ak)m ak+1…an+1 estará en L(M) para todo m³ 0. Es decir, se puede "bombear" cero o más veces la parte central y seguir teniendo una cadena que sea aceptada por el autómata.

El lema de bombeo se define de la siguiente forma:

Sea L un lenguaje regular infinito. Entonces hay una constante n de forma que, sí w es una cadena de L cuya longitud es ³ n, se tiene que w=uvx, siendo uvixÎ L para todo i ³ 0, con |v| ³ 1 y |uv| £ n.

El lema de bombeo facilita una forma de determinar si un lenguaje es regular; de esta forma se podrá decir si es finito y por ello se podrá construir un autómata finito o una expresión regular dada la conexión que existe entre ambos. Recordemos que un lenguaje regular es generado por una expresión regular (para mayor comprensión del tema ver la sección de lenguajes regulares de este capítulo). Para demostrar que un lenguaje no es regular, se mostrará que, cualquier valor n lo bastante grande, se tendrá al menos una cadena de longitud n o mayor que falle al ser "bombeada".

• Por ejemplo: Considérese el lenguaje L={a i | i ³ 1}
• Toda cadena L debe tener una longitud que sea un cuadrado perfecto. Supongamos que L es regular y sea n la constante dada en el lema de bombeo. Obsérvese que an Î L y que, por el lema de bombeo, tenemos an = uvx de forma que 1£ |v| £ n y uvix Î L para todo i ³ 1. Entonces se obtiene que:

n2 = |uvx|

< |uv2x|

£ n2 + n

< (n+1)2

Es decir, la longitud de uv2x se encuentra, estrictamente, entre cuadrados perfectos consecutivos y, por tanto, no es un cuadrado perfecto. Luego uv2x no puede pertenecer a L. Es decir, L no puede ser regular.

EJERCICIOS.

* Ejercicio resuelto.

*2.1. Describa el lenguaje aceptado por el DFA representado por el diagrama de transición de la figura 2.19

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.19.

El lenguaje esta formado por cadenas que tienen cero o más ocurrencias de "ab" y su expresión regular es (ab)*.

2.2. Construya el diagrama de transición y describa el lenguaje que acepta el siguiente autómata finito determinístico: Sea M={Q, S , q0, F, d } dado por:

Q = {q0,q1,q2,q3} S = {0,1}

F = {q0} q0 = q0

y d dada por la tabla de la figura 2.20.

Figura 2.20.

2.3. Proporcione los DFA’S que acepten los siguientes lenguajes sobre el alfabeto {0,1}:

a) El conjunto de todas las cadenas que terminen en 00

b) El conjunto de todas las cadena que posean tres 0’s consecutivos.

*2.4. Dado S ={0, 1} construya el diagrama (ver figura 2.21.) y tabla de transición (ver figura 2.22) para el NFA que acepte el lenguaje formado por todas las cadenas que contengan dos ceros ó dos unos consecutivos.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Figura 2.21.

Figura 2.22.

2.5. Sea M el NFA dado por Q = {q0, q1}, S ={a,b}, q0= q0, F={q1} y d dada en la figura 2.23. Determinar si la cadena "ba" estan en L(M). Dibujar el diagrama de transición para M.

Figura 2.23.

*2.6. Construya los diagramas de transición para los NFA con movimiento e y describa su lenguaje.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

2.7. Construya la tabla de transición y describa el lenguaje que acepta el NFA con movimiento e , dado el diagrama de transición de la figura 2.24.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 *2.8. Encontrar las expresiones regulares correspondientes a las figuras 2.25, 2.26, 2.27 y 2.28

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

Figura 2.25.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Figura 2.26.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 2.27.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 2.28.

*2.9. Describa los lenguajes de las siguientes expresiones regulares:

2.10. Representar por medio de diagramas de transición los DFA’s que acepten las expresiones regulares del ejercicio 2.9.

2.11. Obtener la expresión regular que representa al lenguaje formado por todas las cadenas sobre S ={a, b} que tienen un número par de b’s y construya por medio de un diagrama de transición su DFA.

2.12. Demuestre por medio de un recorrido, que la siguiente definición recursiva pertenece también al conjunto EVEN = {2, 4 ,6 ,8 , …}.

1. 2 y 4 Î EVEN.
2. Si x Î EVEN, entonces también x+4 Î EVEN.

*2.13. Encontrar una función recursiva para el lenguaje generado por una o mas x, es decir, L= x+ = {x, xx, xxx, …}

1. X Î L.
2. Q Î EVEN entonces XQ Î L.
3. Ninguna otra cadena que no sea obtenida por la regla 1 y la regla 2 Î L.

*2.14. Encontrar una función recursiva para el lenguaje palíndrome sobre {0,1}, es decir, PAL = {e , 0, 1, 11, 00, 111, 000, 101, 010, …}.

1. e , 0, 1 Î PAL.
2. X Î PAL entonces 1X1 Î PAL.
3. X Î PAL entonces 0X0 Î PAL.
4. Ninguna otra cadena Î PAL.

2.15. Encontrar una función recursiva para el lenguaje generado por una o mas x, es decir, L= x* = {e , x, xx, xxx, …}

CAPÍTULO III

AUTÓMATAS DE PILA Y

LENGUAJES LIBRES DE CONTEXTO

Objetivo:

El alumno entenderá la fundamentación de lenguajes libres de contexto. Aprenderá a construir gramáticas libres de contexto que definan un lenguaje y su notación BNF, además de aprender a utilizar los autómatas de pila.

3.1. AUTÓMATAS DE PILA O PUSH -DOWN (PDA).

Un autómata de pila o Push-Down es un autómata que cuenta con un mecanismo que permita almacenamiento ilimitado y opera como una pila.

El autómata de pila (se abrevia PDA de sus siglas en inglés Push-Down Autómata) tiene una cinta de entrada, un control finito y una pila. La pila es una cadena de símbolos de algún alfabeto. El símbolo que se encuentra más a la izquierda se considera como que está en la "cima". El dispositivo será no determinístico y tendrá un número finito de alternativas de movimiento en cada situación ver figura 3.1.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 3.1 Autómata de pila.

 Los movimientos serán de dos tipos. En el primer tipo de movimiento se utiliza un símbolo de entrada. Dependiendo del símbolo de entrada, del símbolo de la cima y el estado de control finito, es posible un número de alternativas.

Cada alternativa consiste en un estado posterior para el control finito y una cadena (posiblemente vacía) de símbolos, para sustituir al símbolo que se encuentra en la cima de la pila. Después de seleccionar una alternativa, la cabeza de entrada avanza un símbolo como se ilustra en la figura 3.2.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior  

Figura 3.2 Avance de un símbolo de entrada (q1, c, B), a un estado posterior

y sustitución de la cima de la pila {(q2, B)}.

El segundo tipo de movimiento conocido como movimiento e es parecido al primero, excepto que el símbolo de entrada no se utiliza y la cabeza de la entrada no avanza después del movimiento. Este tipo de movimiento permite al PDA manipular la pila sin leer símbolos de entrada como se muestra en la figura 3.3.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 3.3 Manipulación de la pila sin leer símbolo de entrada.

Existen dos modos de aceptar un lenguaje por un autómata de apilamiento. El primero consiste en definir el lenguaje aceptado como el conjunto de todas las entradas para las cuales una sucesión de movimientos ocasiona que el autómata de pila vacíe su pila.

La segunda manera es designando algunos estados como estados finales y definimos el lenguaje aceptado como el conjunto de todas las entradas para las cuales alguna selección de movimiento ocasiona que el autómata de pila accese un estado final.

Un autómata de pila M es un sistema (Q, S , G , d , q0, Z0, F), en donde:

Q es un conjunto finito de estados.

S es el alfabeto llamado alfabeto de entrada.

G es el alfabeto, conocido como alfabeto de pila.

q0 Î Q, es el estado inicial.

Z0 Î G , es el símbolo llamado símbolo inicial.

F Í Q es el conjunto de estados finales.

d es una transformación de Q x (S È a {e }) x G en los subconjuntos finitos Q x G *.

Sea M=(Q, S , G , d , q0, Z0, F) un autómata de pila. El lenguaje aceptado por M se denota por L(M) y es el conjunto L(M) = {wÎ S *½ ( q0, w, Z0) * (p, e , u ) para pÎ F y uÎ G *}.

Nota: * se usa para denotar los movimientos con un número arbitrario de pasos, donde * indica "cero o más pasos".

Obsérvese que la aceptación requiere que M se mueva a un estado final cuando la cadena w se agote. M puede terminar o no con la pila vacía. (Sin embargo, obsérvese que cuando la pila se vacía el PDA debe parar, ya que todas las transiciones requieren un símbolo de pila).

El siguiente ejemplo representa un autómata de pila que acepta a {wcwR|wÎ (0+1)*} mediante un agotamiento de pila M=(Q, S , G , d , q0, Z0, F). Donde:

Q = {q1, q2} q0 = q1

S = {0, 1, C} Z0 = R

G = {R, B, G} F = Æ

y d está definida por:

1. d (q1, 0, R) = {(q1, BR)}
2. d (q1, 0, B) = {(q1, BB)}
3. d (q1, 0, G) = {(q1, BG)}
4. d (q1, c, R) = {(q2, R)}
5. d (q1, c, B) = {(q2, B)}
6. d (q1, c, G) = {(q2, G)}
7. d (q2, 0, B) = {(q2, e )}
8. d (q2, e , R) = {(q2, e )}
9. d (q1, 1, R) = {(q1, GR)}

10. d (q1, 1, B) = {(q1, GB)}
11. d (q1, 1, G) = {(q1, GG)}
12. d (q2, 1, G) = {(q2, e )}

Analizando la cadena 01C10 usando el PDA anterior se obtiene lo siguiente:

(q1, 01C10, R) por la regla 1 ® (q1, 1C10, BR) por la regla 10 ® (q1, C10, GBR) por la regla 6 ® (q2, 10, GBR) por la regla 12 ® (q2, 0, BR) por la regla 7 ® (q2, e , R) por la regla 8 ® (q2, e , e ) y se agota la pila.

Consideremos el siguiente ejemplo de autómata de pila definido por:

Q = {q1, q2, q3, q4}

S = {a, b}

G = {A,B}

Z0 = A

F = {q4}

q0=q1

y d dado por la siguiente tabla:

Ya que d depende del estado actual, el símbolo de entrada actual y el símbolo actual de la cima de la pila, la tabla tiene filas que corresponden a los estados y columnas que corresponden a los pares de símbolos de entrada y de la pila.

Obsérvese que no hay transiciones para todas las ternas posibles de estado, símbolo de entrada y símbolo de pila. Por lo tanto, si el PDA pasa a un estado para el cual no se especifica un estado siguiente y una acción de la pila para los símbolos actuales de la pila y la entrada, el PDA no puede volver a realizar ningún movimiento. En particular, cuando el autómata está en el estado q4, que es el estado de aceptación, no hay ninguna transición sea cual sea el símbolo de la cima y de la entrada.

Si el PDA se mueve al estado q2, entonces obsérvese que cada vez que a aparece en la entrada se apila una B en la pila. El PDA permanece en el estado q2 hasta que se encuentra la primera b y entonces se mueve al estado q3, ninguna b puede preceder a una a. Finalmente, en el estado q3 sólo se consideran las b’s y, cuando se encuentra cualquier b, se desapila B de la pila. (Sólo pueden desapilarse las B’s que fueron apiladas, debido a encontrarse una a en la entrada).

Las únicas cadenas que acepta el PDA pertenecen al lenguaje {an bn | n³ 0}È {a}, puesto que son las únicas cadenas de entrada que, una vez que han sido consumidas, causan que el PDA termine en el estado final q4.

3.2. GRAMÁTICAS LIBRES DE CONTEXTO (CFG’S).

Las gramáticas libres de contexto amplían la capacidad para especificar lenguajes al incluir algunos lenguajes que no son reconocidos por un autómata finito.

Las gramáticas libres de contexto son útiles para describir expresiones aritméticas que tengan una anidación arbitraria de paréntesis balanceados y estructuras de bloque en los lenguajes de programación.

Las características de las gramáticas libres de contexto son:

1. Un alfabeto S de caracteres llamados símbolos terminales con los cuales se obtienen cadenas que forman las palabras de un lenguaje.
2. Un conjunto de símbolos no terminales, uno de los cuales es el símbolo S conocido como símbolo inicial.

3. Un conjunto finito de producciones de la forma

Un no terminal ® cadenas finitas de terminales y/o no terminales.

Donde las cadenas de terminales y/o no terminales pueden tener solo terminales, solo no terminales, o cualquier combinación de terminales y no terminales o incluso a la cadena vacía. Se requiere al menos una producción que tenga el no terminal S del lado izquierdo.

Por lo general los no terminales se representan por letras mayúsculas mientras que los terminales se designan por letras minúsculas y símbolos especiales.

Una gramática libre de contexto (se abrevia CFG de sus siglas en inglés Context-Free Grammar) es una 4-tupla G=(V, T, P, S) donde:

V es una colección finita de símbolos no terminales

T es un alfabeto (también conocido como conjunto de símbolos terminales)

VÇ T=Æ no tienen símbolos comunes.

P es un conjunto finito de producciones, cada producción es de la forma A ® a , en donde A es una variable y a es una cadena de símbolos tomados de (VÈ T)*.

S es una variable conocida como símbolo inicial.

El lenguaje generado por la gramática libre de contexto G se denota por L(G) y se llama lenguaje libre de contexto (se abrevia CFL de sus siglas en inglés Context-Free Language).

Por ejemplo la siguiente gramática genera el lenguaje a n donde n ³ 1.

S ® a

S ® aS

Donde:

V= {S}, T= {a}, S= S y P= {S ® a, S ® aS}

Otro ejemplo: Diseñe una CFG que genere el lenguaje 0n12n | n ³ 1.

S ® 011

S ® 0S11

El lenguaje generado por una gramática se demuestra con el siguiente ejemplo:

V= {S}, T= {a, b}, P= {S ® aSb, S ® ab} y S= S

Usaremos la notación Þ para indicar el acto de generar (como opuesto a ® , el cual es parte de una regla de producción). Cuando derivamos una cadena, los no terminales representan la parte de la cadena que todavía no se ha generado, puede haber más de un trozo no generado y pueden aparecer en cualquier lugar de la cadena. Cuando la derivación se completa, todos los trozos no generados habrán sido sustituidos por cadenas (posiblemente vacías) de símbolos terminales.

Así pues tenemos S Þ aSb Þ aaSbb Þ a3Sb3 Þ … Þ an-1Sbn-1 Þ anbn su lenguaje es L(G) = {anbn | n ³ 1}

Todas las cadenas que no tengan símbolos no terminales pertenecen al lenguaje definido por G que puede ser producido por el símbolo inicial S usando las producciones como sustituciones.

3.3. PUMPING LEMMA PARA LENGUAJES LIBRES DE CONTEXTO.

El planteamiento formal del lema de bombeo (Pumping Lemma en inglés) para CFL’s es el siguiente:

Sea L un lenguaje libre de contexto que no contiene e . Entonces existe un entero k para el cual, si z Î L y ½ z½ >k , entonces z se puede volver a escribir como z = uvwxy con las propiedades siguientes:

1. ½ vwx½ £ k.
2. Al menos v o x no es e .
3. uvi wxi y Î L para todo i ³ 0.

Al igual que el lema de bombeo para lenguajes regulares, el lema de bombeo para lenguajes libres de contexto nos proporciona la posibilidad de probar si ciertos lenguajes no son libres de contexto, por tanto, utilizaremos el mismo planteamiento que en el caso de los lenguajes regulares.

Supongamos que L ={ ai bj | j= i2} es libre de contexto, entonces se puede aplicar el lema de bombeo y por tanto habrá un k que satisfaga las condiciones del lema. Consideremos z= ak bk2.

Desde luego, z Î L y ½ z½ >k. Por tanto, z se puede descomponer en z=uvwxy y se puede asegurar que uvi wxi y Î L para todo i ³ 0, tal que ½ vxz½ >1 y ½ vwx½ £ k. Obsérvese que, si v= ar bs para algún r y s, entonces vi= (ar bs) i y, por tanto, uvi wxi y tiene b’s antes de a’s con lo que no puede pertenecer a L. De forma similar, si x= ar bs, tampoco pueden ser bombeados. Por lo que debemos obtener que:

v= ar y x= as o

v= br y x= bs o también

v= ar y x= bs

para algún valor de r y s. En el primer caso se tiene uv2 wx2 y= ak+r+sbk2

En el segundo caso tenemos uv2 wx2 y= akbk2+r+s

En ambos casos, cuando al menos uno de los dos r o s, son ³ 1 (como se requiere en el lema de bombeo), la cadena resultante no puede pertenecer a L. En el tercer caso, se obtendrá uvi wxi y= ak+(i-1)rbk2+(i-1)s el cual no pertenece a L para toda i a excepción de un número finito. Por tanto, L no puede ser libre de contexto puesto que para él no se cumple el lema de bombeo.

3.4. NOTACIÓN BNF.

Todo lenguaje de programación tiene reglas que prescriben la estructura sintáctica de programas bien formados. Se puede describir la sintaxis de las construcciones de los lenguajes de programación por medio de gramáticas libres de contexto o notación BFN (de sus siglas en inglés Backus-Naur Form que significa Forma de Backus-Naur ), utilizando la siguiente simbología:

< > significa no terminal

: : = significa produce

Þ significa deriva

Ejemplo: El siguiente lenguaje genera cadenas de acuerdo con la expresión regular (a+b)*c

< S > : : = a < S >

< S > : : = b < S >

< S > : : = c

El ejemplo anterior da cómo resultado:

< S >Þ a < S >

a < S >Þ ab < S >

ab < S > Þ abc

Ejemplo. Describir el lenguaje generado por la gramática

< P > : : = Procedure Id Begin < Inst > End.

< Inst > : : = instrucción

< Inst > : : = instrucción ; < Inst>

Lo anterior genera programas con una estructura muy general, similar a los programas en Pascal. Ejemplo:

< P >Þ Procedure Id Begin < Inst > End.

< Inst >Þ Procedure Id Begin instrucción; < Inst > End.

< Inst >Þ Procedure Id Begin instrucción; instrucción; < Inst > End.

< Inst >Þ Procedure Id Begin instrucción; instrucción; instrucción End.

Lo anterior se logra apreciar mejor como se muestra a continuación:

Procedure Id

Begin

Instrucción;

Instrucción;

Instrucción

End.

3.5. ARBOLES SINTACTICOS.

Cuando una cadena se deriva mediante una gramática libre de contexto, el símbolo inicial es sustituido por alguna cadena. Los símbolos no terminales de esta cadena son sustituidos uno tras otro por otra cadena, y así sucesivamente, hasta que se llega a una cadena formada sólo por símbolos terminales. A veces, es útil realizar un gráfico de la derivación, que indique de qué manera ha contribuido cada no terminal a formar la cadena final de símbolos terminales. Tal gráfico tiene forma de árbol y se llama árbol sintáctico.

Un árbol sintáctico para una derivación dada se construye creando un nodo raíz que se etiqueta con el símbolo inicial. El nodo raíz tiene un nodo hijo para cada símbolo que aparezca en el lado derecho de la producción usada para reemplazar el símbolo inicial. Todo nodo etiquetado con un no terminal también tiene nodos hijos etiquetados con los símbolos del lado derecho de la producción usada para sustituir ese no terminal. Los nodos que no tienen hijos deben ser etiquetados con símbolos terminales.

Consideremos la CFG cuyo lenguaje es: {ambn | m ³ 1 y n ³ 1}

S ® AB

A ® aA | a

B ® bB | b

La cadena aabbb puede ser derivada para la anterior CFG mediante.

S Þ AB Þ AbB Þ AbbB Þ Abbb Þ aAbbb Þ aabbb

En la figura 3.4 se presenta un árbol sintáctico para esta derivación.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 3.4.

 Finalmente, puede verse que hay muchas derivaciones posibles para la cadena aabbb, las cuales también tienen el árbol de derivación anterior. Por ejemplo:

S Þ AB Þ aAB Þ aaB Þ aabB Þ aabbB Þ aabbb.

y S Þ AB Þ aAB Þ aAbB Þ aAbbB Þ aAbbbÞ aabbb.

Para esta cadena y esta gramática, todas las derivaciones de aabbb tienen el mismo árbol de derivación. Sin embargo, esto no tiene porque cumplirse siempre. Para verlo, considérese la siguiente gramática que genera expresiones aritméticas simples con los operadores: +, -, *, /, ­ , ( ).

S ® id

S ® S+S | S-S

S ® S*S | S/S

S ® S­ S | -S

S ® (S)S

Podemos derivar la expresión id+id*id de dos formas distintas como sigue:

1. S Þ S+SÞ S+S*S Þ S+S*id Þ S+id*id Þ id+id*id
2. SÞ S*SÞ S+S*SÞ id+S*SÞ id+id*SÞ id+id*id

El árbol sintáctico para la derivación uno es

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Mientras que el árbol para la derivación dos es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Observe que los dos árboles anteriores son distintos, aunque las cadenas producidas son las mismas.

Una gramática se dice que es ambigua si hay dos o más árboles sintácticos distintos.

La ambigüedad puede ser un problema para ciertos lenguajes en los que su significado depende en parte de su estructura, como ocurre con los lenguajes naturales y los lenguajes de programación. Si la estructura de un lenguaje tiene más de una descomposición y si la construcción parcial determina su significado, entonces el significado es ambiguo.

Por convención, si dos formas de generar una cadena tienen una única salida. En una derivación por la izquierda, el no terminal que se expande es siempre el del extremo izquierdo.

Una derivación por la derecha es aquella en la cual el no terminal que se expande es el del extremo derecho.

Una gramática ambigua se caracteriza por tener dos o más derivaciones por la izquierda para la misma cadena.

EJERCICIOS.

* Ejercicio resuelto.

*3.1. Obtener el autómata de pila para el siguiente lenguaje {an | n ³ 1}.

Q= {q1, q2}, S = {a}, G = {Zo}, el símbolo inicial de la pila, q0= q1, F= {q2} y d viene dado por la siguiente tabla:

*3.2. Dado el siguiente autómata de pila M=(Q, S , G , d , q0, Z0, F) describir el lenguaje aceptado.

Q= {q1, q2}, S = {a, b}

G = {A, B, Z}, q0= q1

Z0= Z, F= {q2}

y d viene dado por la lista siguiente:

1. d (q1, e , Z)= {(q2, Z)}
2. d (q1, a, Z)= {(q1, AZ)}
3. d (q1, b, Z)= {(q1, BZ)}
4. d (q1, a, A)= {(q1, AA)}
5. d (q1, b, A)= {(q1, e )}
6. d (q1, a, B)= {(q1, e )}
7. d (q1, b, B)= {(q1, BB)}

L= {w Î {a, b}*| w contiene la misma cantidad de a’s que de b’s}.

Cuenta el número de ocurrencias de a’s y b’s. Esto puede realizarse introduciendo símbolos en la pila cuando se lee algún carácter de entrada y extrayéndolo cuando se lee otro.

3.3. Dado que en un PDA los símbolos pueden ser recuperados de la pila en orden inverso a como fueron introducidos. Consideremos el lenguaje L= {wcwI | w Î {a, b}*}. Este PDA debe introducir los caracteres de entrada en la pila hasta que se encuentra una c y, entonces, compara los caracteres de la entrada con la cima de la pila, desapilando la pila si concuerda. Describir el proceso que realiza dicho autómata de pila M=(Q, S , G , d , q0, z0, F) sobre las cadenas: abcba, abcab, y babbcbbab.

Q= {q1, q2, q3}, S = {a, b}

G = {a, b, z}, q0= q1

Z0= símbolo inicial de la pila

F= {q3}, y d viene dado por la lista siguiente:

1. d (q1, a, z)={(q1, az)}
2. d (q1, a, a)={(q1, aa)}
3. d (q1, a, b)={(q1, ab)}
4. d (q1, b, z)={(q1, bz)}
5. d (q1, b, a)={(q1, ba)}
6. d (q1, b, b)={(q1, bb)}
7. d (q1, c, z)= {(q2, z)}
8. d (q1, c, a)= {(q2, a)}
9. d (q1, c, b)= {(q2, b)}
10. d (q2, a, a)= {(q2, e )}
11. d (q2, b, b)= {(q2, e )}
12. d (q2, e , z)= {(q3, z)}

3.4. Describa el lenguaje que será aceptado por el autómata de pila M=(Q, S , G , d , q0, z0, F) dado a continuación:

Q= {q1, q2, q3}

S = {a, b}

G = S È {Z0}, donde Z0 es el símbolo inicial de la pila

q0= q1

F= {q3}

y d viene dado por la siguiente tabla:

*3.5. Determinar la expresión regular equivalente a la siguiente CFG.

S ® aS

S ® bS

S ® a

S ® b

S ® e

La expresión regular es (a+b)*

*3.6. Diseñar una CFG equivalente a la expresión regular :

(a+b)*aa(a+b)*.

S ® XaaX

X ® aX

X ® bX

X ® e

3.7. Encontrar una CFG para cada uno de los lenguajes definidos por las siguientes expresiones regulares.

1. ab*
2. a*b*
3. (baa + abb)*

*3.8. Diseñe una CFG que genere los siguientes lenguajes:

2. 0n1n | n ³ 0
3. ai+3 b2i+2 | i ³ 0

c) 0i 1j 0k | j>i+k

a) S ® e b) S ® aaabb c) S ® ABC

S ® 0S1 S ® aSbb A ® 0A1| e

B ® 1B|1

C ® 1C0| e

3.9. En cada caso, diga que lenguaje es generado por las CFG’s indicadas en las siguientes producciones:

a) S ® aSa | bSb | e

b) S ® aSa | bSb | a | b

c) S ® aS | aSbS | e

d) S ® aS | bS | a

3.10. Probar que los siguientes lenguajes son libres de contexto, utilizando el lema de bombeo.

a) {ai bi ci | i ³ 1 }

b) {ai bj ci dj | i ³ 1 y j ³ 1 }

*3.11. Diseñar una CFG que genere cadenas de paréntesis balanceados. Ejemplos: ( ( ( ) ) ), ( ( ( ) ( ) ) ).

S ® e

S ® (S)S

*3.12. Diseñar un CFG (en notación BNF) que genere nombres de identificadores.

< Ident > : : = < Letra > < Más_símbolos >

< Más_símbolos > : : = e | < Letra > < Más_símbolos > |

| < Dígito > < Más_símbolos >

< Letra > : : = A | B | … | Z | a | b | … |z

< Dígito > : : = 0 | 1 | … | 9

3.13. Diseñar un CFG (en notación BNF) que genere cadenas de listas de identificadores.

*3.14. Considerando la gramática del ejercicio 3.11. encontrar los árboles sintácticos para las cadenas: a) ( ) ( ) ( ), b) ( ( ) ( ) ) y c) ( ( ) ) ( )

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

CAPÍTULO IV

AUTÓMATAS LINEALES Y

LENGUAJES SENSIBLES AL CONTEXTO

Objetivo:

El alumno aprenderá a utilizar los autómatas lineales acotados, construirá gramáticas sensibles al contexto y entenderá su aplicación en los lenguajes naturales.

4.1. AUTÓMATAS LINEALES (LBA).

Un autómata lineal acotado (LBA de sus siglas en inglés Linear-Bounded Autómata) es una máquina de Turing no determinística (para mayor comprensión del tema vea el capítulo V de Máquinas de Turing) que satisface las siguientes dos condiciones:

1. El alfabeto de entrada de cinta incluye dos símbolos: < y >, los señaladores de extremo izquierdo y derecho, respectivamente.
2. El LBA no tiene movimientos a la izquierda de < o a la derecha de >, ni puede sustituir los símbolos < y >.

Definiremos un autómata linealmente acotado como una máquina de Turing no determinista M=(Q, S , G , d , q0, B, F), en la cual el alfabeto de cinta contenga dos símbolos especiales < y >. M comienza con la configuración (q1 , £ w>) (donde q1 es el estado inicial de M). No se permite que M reemplace los símbolos < o >, ni que mueva su cabeza a la izquierda de < o a la derecha de >, con lo cual, el LBA tiene que realizar su computación en las únicas celdas de la cinta que estaban originalmente ocupadas por la cadena de entrada.

Por ejemplo, consideremos el LBA definido por:

Q ={q1, q2}, S ={a, b}, G ={a, b, <, >}, F ={q2}, q0 =q1 y d dado por:

d (q1, <) = (q1, <, R)

d (q1, a) = (q1, b, R)

d (q1, b) = (q1, a, R)

d (q1, >) = (q1, >, S), donde S significa "permanecer", es decir no mover la cabeza de lectura/escritura. Este LBA complementa sus cadenas de entrada convirtiendo las a’s en b’s y viceversa. Obsérvese que, aunque puede reconocer y trabajar sobre los símbolos < y >, no puede reemplazarlos o moverse más allá de ellos. Supongamos que un LBA comienza siempre con su cabeza situada sobre el símbolo <.

4.2. LENGUAJE NATURAL O SENSIBLE AL CONTEXTO.

Para entender que es un lenguaje natural tenemos que ver antes que es la Inteligencia Artificial (AI, de sus siglas en inglés Artificial Intelligence).

La Inteligencia Artificial, es un área de las ciencias computacionales que nació con el objetivo de estudiar actividades humanas, es decir, se basa en estudiar la forma en que los seres humanos piensan cuando tratan de tomar decisiones y resolver problemas. Estos procesos de pensamiento se descomponen en sus pasos básicos, que después se usan para diseñar programas de computadora que resuelvan esos mismos problemas a través de un proceso similar.

Algunos de los trabajos que se han desarrollado en Inteligencia Artificial abarcan diversas áreas de investigación, tales como la simulación de capacidades perceptuales y habilidades psicomotoras (Robótica), la comprensión del lenguaje natural y la construcción de sistemas informáticos capaces de emular la pericia de un experto humano en un ámbito de conocimiento determinado (Sistemas Expertos).

El lenguaje es la forma en que nos comunicamos cotidianamente con el mundo, es decir como el hombre sé interrelaciona con su medio. La mayor parte de la comunicación se lleva a cabo en forma de voz. El lenguaje escrito juega un papel no tan central como el lenguaje hablado en muchas actividades. Pero el procesamiento del lenguaje escrito (suponiendo que está escrito con caracteres no ambiguos) es menos complejo que la comprensión del habla. Por ejemplo, para construir un programa que comprenda el lenguaje oral, es necesario disponer de todas las características de uno que entienda el lenguaje escrito junto el conocimiento adicional que es necesario para poder manipular todos los ruidos y las ambigüedades de la señal de audio.

Para el procesamiento del lenguaje escrito, usualmente denominado lenguaje natural se requieren conocimientos léxico, sintáctico y semántico sobre el lenguaje, además de la información que se necesita sobre el mundo real. El procesamiento del lenguaje natural incluye tanto comprensión como generación.

Por último, para analizar el entendimiento entre las personas (que hablan el mismo idioma) muchas veces resulta difícil la interpretación del mensaje, ya sea por los modismos, la entonación, etc., por lo que para lograr la comprensión del lenguaje natural, se requiere de amplios conocimientos lingüísticos, así como del manejo de lenguajes de programación de muy alto nivel, por ejemplo: Prolog y Lisp.

Ahora ya con una visión global de los inicios del lenguaje natural, es necesario tener en cuenta que al comenzar a construir programas informáticos que lo comprendan, se debe conocer a detalle los distintos componentes que se involucran en el proceso de su comprensión. Dicho proceso se divide en las siguientes partes [Knight Rich]:

1. Análisis morfológico: Se analizan los componentes de las palabras individuales y se separan de ellas los constituyentes que no forman parte de ellas, como los símbolos de puntuación.
2. Análisis sintáctico: Se transforman las secuencias lineales de palabras en ciertas estructuras que muestran la forma en que se relacionan entre sí. Se pueden rechazar algunas secuencias si infringen las reglas del lenguaje sobre la forma de combinarse. Por ejemplo: un analizador sintáctico de castellano rechazaría la frase "Chico el va almacén al".
3. Análisis semántico: Se les asigna significados a las estructuras creadas por el analizador sintáctico. En otras palabras, se hace una correspondencia entre las estructuras sintácticas y los objetos del dominio de la tarea. Las estructuras en las que no se puede hacer esta correspondencia se rechazan. Por ejemplo: en la mayoría de los universos "las ideas verdes incoloras duermen" serían rechazadas por ser semántica anómala.
4. Integración del discurso: El significado de una frase individual puede depender de las precedentes e influenciar el significado de otras posteriores. Por ejemplo: la palabra "lo" en "Juan lo quiso" depende del contexto del discurso, mientras que la palabra "Juan" puede influenciar el significado de frases posteriores como "Él siempre lo tuvo".
5. Análisis de la pragmática: La estructura que representa se reinterpreta para determinar su significado actual. Por ejemplo, la frase ¿sabe usted qué hora es? debería interpretarse como una petición de la hora.

Además se debe considerar que el lenguaje natural no reconoce declaraciones que estén fuera de su campo de acción, de su forma de análisis gramatical o de su contexto de interpretación de declaraciones por lo que algunos grandes problemas del lenguaje natural son la ambigüedad y las declaraciones con más de un significado.

En este último aspecto es necesario analizar algunos tipos de ambigüedades:

1. 1. armadura para cubrir la cabeza
   2. las uñas de las patas de los caballos
   3. cuerpos de los barcos, etc.
2. Ambigüedad léxica: Una palabra puede tener varios significados. Por ejemplo, la frase "Tenía los cascos sin herrar", la palabra "cascos" puede significar:
   1. Debes comprar peras y manzanas o debes comprar duraznos
   2. Debes comprar peras y debes comprar manzanas o duraznos.
3. Ambigüedad estructural: Una frase puede tener dos o más estructuras sintácticas. Por ejemplo: la frase "Debes de comprar peras y manzanas ó duraznos" se puede interpretar como:
   1. Del verbo cocinar
   2. Del sustantivo cocina.
4. Ambigüedad de clase: Una palabra puede ser tomada como verbo o como nombre. Ejemplo: "Mamá está en la cocina", aquí la palabra cocina proviene de:
   2. Que la vio a través de los lentes del telescopio

   3. Que la vio que llevaba un telescopio.
5. Ambigüedad global: La frase es completamente ambigua. Ejemplo: "Juan vio a la muchacha con telescopio", esta oración puede interpretarse como:
6. Significado de la frase: También es conocida como representación objetivo, la cual se refiere que una frase se puede interpretar de diferentes formas, como por ejemplo: ¿Sabes que hora es?. La interpretación sería: si sabes la hora, dímela.
7. Metáforas: Figuras que trasladan las palabras reales a un sentido figurado. Por ejemplo: "Son tus ojos como dos esmeraldas". Esto nos dice: Que sus ojos son verdes y hermosos.
8. Modismos: Son expresiones propias y privadas de la lengua. Cada región tiene la propia. Por ejemplo: "A la chita callando", lo cual significa: Callarse la voz de ya.

Podemos especificar un lenguaje por medio de dos técnicas. La primera es describiendo un procedimiento para reconocer sus cadenas, es decir, a través de autómatas de varios tipos y la segunda forma es por medio de una técnica que genere sus cadenas, esto es con la utilización de gramáticas. Para tener una mejor idea sobre este último método veremos la siguiente gramática simple para un lenguaje.

Oración ® Sujeto + Predicado

Sujeto ® Artículo + Sustantivo

Sujeto ® Sustantivo

Predicado ® Verbo + Sujeto2

Sujeto 2 ® Artículo + Sustantivo

Sujeto 2 ® Artículo + Sustantivo + Adjetivo

La primera producción establece que una oración esta compuesta de un sujeto y un predicado, el sujeto puede ser un artículo seguido de un sustantivo o un sustantivo únicamente. El predicado consta de un verbo y un sujeto que es ligeramente diferente al primer sujeto, esta frase puede tener ya sea en un artículo más un sustantivo o un artículo seguido por un sustantivo y después un adjetivo. El árbol para esta gramática se muestra en la figura 4.1.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 4.1. Árbol para una gramática simple de un lenguaje.

Utilizando la gramática y un vocabulario formado por artículos, adjetivos, verbos y sustantivos se pueden crear oraciones significativas en español.

La forma en que se va a realizar el almacenamiento del vocabulario depende del lenguaje de programación que se use los más utilizados son: Prolog o Lisp o incluso lenguaje "C". Los dos primeros nos permiten de una manera fácil y abundante el manejo de gráficos y de base de datos, en cuanto se refiere al tercero facilita el manejo de gráficos pero no muy sencillo en el manejo de base de datos.

Ahora bien existe una gramática más útil para el desarrollo de lenguajes naturales y se conoce como gramática sensible al contexto.

Las gramáticas sensibles al contexto (CSG de sus siglas en inglés Context-Sensitive Grammar) producen una clase de lenguajes que está estrictamente situada entre los lenguajes libres de contexto y los lenguajes recursivos y se conocen como lenguajes sensibles al contexto (CSL de sus siglas en inglés Context-Sensitive Language).

Una gramática G=(N, S , S, P) es una gramática sensible al contexto si todas las producciones son de la forma a ® b , donde a , b , Î (N È S )+ y |a | £ |b |. Donde:

N es un alfabeto de símbolos no terminales.

S es un alfabeto de símbolos terminales con NÇ S =Æ .

SÎ N es el símbolo inicial.

P es un conjunto finito de producciones de la forma a ® b , donde a , b , Î (N È S )+.

Por ejemplo, la gramática dada por:

S ® abc|aAbc

Ab ® bA

Ac ® Bbcc

bB ® Bb

aB ® aa|aaA

es una gramática sensible al contexto. Esta gramática genera el lenguaje sensible al contexto {an bn cn| n³ 1}, con lo que tenemos un ejemplo de un lenguaje sensible al contexto que no es libre de contexto.

Toda gramática libre de contexto se puede poner en forma normal de Chomsky, en la cual las producciones son de la forma A® a o también AÞ BC. Puesto que las producciones de esta forma satisfacen la definición de gramáticas sensibles al contexto, se deduce que toda gramática libre del contexto es también una gramática sensible al contexto. Por tanto el conjunto de los lenguajes sensibles al contexto contiene el conjunto de los lenguajes libres de contexto.

La restricción de que el lado derecho de las producciones en una gramática sensible al contexto sea al menos tan largo como el lado izquierdo hace que la gramática sea no contráctil. Puesto que la cadena vacía tiene longitud 0, podemos definir que e Ï L(G), para cualquier gramática G sensible al contexto.

Los lenguajes sensibles al contexto son exactamente los lenguajes aceptados por los autómatas lineales acotados, máquinas de Turing no determinísticas en donde la cabeza de la cinta visita un número de celdas que son una constante múltiple de la longitud de una cadena de entrada.

Los lenguajes sensibles al contexto contienen, propiamente, a los lenguajes libres de contexto. A su vez, los lenguajes recursivos contienen propiamente a los lenguajes sensibles al contexto, como se vio en la clasificación de las gramáticas (ver capítulo 1).

4.3. APLICACIONES.

Existe un gran número de problemas de diseño de software que se simplifican mediante la conversión automática de las expresiones regulares a una instrumentación eficiente de computadora del autómata finito correspondiente.

Los autómatas finitos se usan frecuentemente en los problemas que implican el análisis de cadenas de caracteres. Tales problemas incluyen problemas de búsqueda e identificación, tales como la búsqueda de la existencia de una cadena en un archivo o el reconocimiento de cadenas de entrada que satisfagan ciertos criterios. Un autómata finito es, él mismo, un modelo de un procedimiento para reconocimiento de cadenas por medio de la expresión regular asociada. Por tanto, en la búsqueda de una cadena en un archivo, podemos aplicar el autómata finito de forma sistemática a las cadenas del archivo hasta que se acepta la cadena o se termina el archivo.

Un problema común en la programación de computadoras es el de tener la seguridad de que los datos de entrada de un programa son correctos. La programación cuidadosa pretende construir un programa que analice la información introducida por el usuario y, de alguna forma, prevenir que se aplique información incorrecta al programa. Si pudiéramos construir un autómata finito que aceptara solamente las cadenas que representan información correcta, entonces tendríamos un modelo para dicha rutina de entrada. Puesto que los autómatas finitos se corresponden con las expresiones regulares, el problema se reduce a especificar la información correcta por medio de expresiones regulares.

Por ejemplo, en el caso de que la entrada a un programa esté formado por enteros sin signo, el lenguaje vendrá dado por L={1, 2, 3, 4, 5, 6, 7, 8, 9}.{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}*. Es fácil construir un autómata finito que acepte L (ver Figura 4.2.).

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 4.2.

También es sencillo traducir el autómata finito a un código en un lenguaje de programación; sólo se necesita seguir el rastro de la posición actual en la cadena y del estado actual. A la vez que se recorre la cadena, se comprueba a qué estado se ha llegado y, según eso, se acepta o se rechaza la cadena.

Las expresiones regulares se pueden usar para especificar las unidades léxicas presentes en un lenguaje de programación. Los autómatas finitos asociados se usan para reconocer dichas unidades (llamados componentes léxicos). Dicho análisis es una etapa importante en la compilación de programas de computadoras.

En la etapa de análisis léxico de un compilador, hay un aspecto que no estaba presente en el ejemplo de los enteros como entrada y es el hecho de que al tratar de reconocer un lexema se tienen distintas posibilidades. Por ejemplo, si es un comentario, un identificador, etc. Generalmente, en un compilador, el autómata finito que reconoce todos los componentes léxicos está ordenado de alguna manera y, sistemáticamente, se aplica a la cadena hasta que se tiene éxito o falla en todo. Si falla, la cadena no puede formar parte de un programa.

Otro ejemplo de aplicaciones son los editores de texto. Ciertos editores de texto y programas similares permiten la sustitución de una cadena por cualquier cadena que concuerde con una expresión regular. Por ejemplo, el editor de texto UNIX permite que un comando como s/bbb*/b/ sustituya por un solo espacio en blanco la primera cadena de dos o más espacios en blanco que se encuentran en una línea dada. La expresión "cualquier" que se representa por el * denota a1+a2+…+an, en la que las ai son todos los caracteres de una computadora excepto al carácter "nueva línea". Podemos convertir una expresión regular r a un autómata finito determinístico (DFA) que acepte cualquier *r. Nótese que la presencia de la operación cualquier* nos permite reconocer un miembro de L(r) que comience en cualquier lugar de la línea. Sin embargo, la conversión de una expresión regular a un DFA toma mucho más tiempo que el que toma barrer una sola línea corta utilizando el DFA, y el DFA podría tener cierto número de estados que son una función exponencial de la longitud de la expresión regular.

Lo que realmente sucede en el editor de textos de UNIX es que la expresión regular cualquier *r es convertida a un autómata finito no determinístico (NFA) con transiciones e , y el NFA se simula directamente. Sin embargo, una vez que se ha construido una columna, listando todos los estados en los que puede estar el NFA sobre un prefijo determinado de la salida, la columna inmediata anterior ya no es necesaria y se elimina con el fin de ahorrar espacio.

EJERCICIOS:

* Ejercicio resuelto.

*4.1. Obtener un LBA que acepte el lenguaje {an| n ³ 0}.

Q ={q1, q2, q3} S ={a, b}

G ={a, b, <, >} F ={q3}

q0 =q1 y d dado por:

1. d (q1, <) = (q1, <, R)
2. d (q1, a) = (q1, a, R)
3. d (q1, b) = (q2, b, R)
4. d (q2, a) = (q2, a, R)
5. d (q2, b) = (q2, b, R)
6. d (q1, >) = (q3, >, S)

*4.2. Obtener un LBA que acepte el lenguaje {an bn | n ³ 1}.

Q ={q1, q2, q3, q4, q5} S ={a, b}

G ={a, b, c, d, <, >} F ={q5}

q0 =q1 y d dado por:

1. d (q1, <) = (q1, <, R)
2. d (q1, a) = (q2, c, R)
3. d (q2, a) = (q2, a, R)
4. d (q2, d) = (q2, d, R)
5. d (q2, b) = (q3, d, L)
6. d (q3, d) = (q3, d, L)
7. d (q3, a) = (q3, a, L)
8. d (q3, c) = (q1, c, R)
9. d (q1, d) = (q4, d, R)
10. d (q4, d) = (q4, d, R)
11. d (q4, >) = (q5, >, S)

4.3. Obtener un LBA que acepte el lenguaje {an bn cn | n ³ 1}.

4.4. Obtener un LBA que determine si sus cadenas de entrada tienen longitud impar. Suponga que las cadenas de entrada pertenecen a {a, b}*.

*4.5. Si una gramática sensible al contexto puede contener la producción S® e , ¿Por qué se requiere que S nunca aparezca en el lado derecho de una producción?.

Por que las gramáticas sensibles al contexto tienen la restricción de no ser contráctil. Puesto que la cadena vacía tiene longitud 0 se tiene entonces que e Ï L(G) a cualquier gramática sensible al contexto.

*4.6. Describa el lenguaje generado por la siguiente gramática sensible al contexto:

S ® Xb

Xb ® bA

El lenguaje es {b2 | i ³ 1 }.

Ejemplos de la derivación:

b2 b2 b2

S Þ Xb S Þ Xb S Þ Xb

Þ bb Þ bXbb Þ bXbb

Þ bbbb Þ bbXbbb

Þ bbbbbb

*4.7. Construya la gramática sensible al contexto que genere el lenguaje {an bm cm dn | m,n³ 1}.

S ® aSd | aAdd

Ad ® bAdc | bc

Ejemplos de la derivación:

a1 b1 c1 d1 a2 b1 c1 d2 a2 b2 c2 d2

S Þ aAdd S Þ aSd S Þ aSd

Þ abcd Þ aaAddd Þ aaAddd

Þ aabcdd Þ aabAdcdd

Þ aabbccdd

*4.8. Construya la gramática sensible al contexto que genere el lenguaje {a2i| i³ 1}.

1. S ® [AcaB]
2. [Ca]a ® aa[Ca]

[Ca] [aB] ® aa[CaB]

[ACa]a ® [Aa]a[Ca]

[ACa] [aB] ® [Aa]a[CaB]

[ACaB] ® [Aa][aCB]

[CaB] ® a[aCB]

3. [aCB] ® [aDB]
4. [aCB] ® [aE]

   [aDB] ® [DaB]

   [Aa] [Da] ® [ADa]a

   a[DaB] ® [Da] [aB]

   [Aa] [DaB] ® [ADa] [aB]

5. a[Da] ® [Da]a
6. [ADa] ® [ACa]

   [aE] ® [Ea]

   [Aa] [Ea] ® [AEa]a

7. a[Ea] ® [Ea]a
8. [AEa] ® a

Nota: A, B, C, etc. no son más que señaladores, que a fin de cuentas, desaparecerán. En lugar de utilizar símbolos separados para los señaladores, se pueden incorporar estos señaladores a las a’s mediante la creación de variables "compuestas" como [CaB], que son un solo símbolo que aparece en lugar de la cadena.

4.9. ¿El conjunto de los lenguajes sensibles al contexto es cerrado con respecto a la unión, la concatenación o la cerradura de estrella? ¿Por qué?.

4.10 Construya la gramática sensible al contexto que genere los siguientes lenguajes:

1. {an | n³ 1 }
2. {ww | w Î {a, b}+}.
3. {w | w Î {a, b, c}* y el número de a’s en w es igual al número de b’s y c’s}.
4. {am bn am bn | m,n³ 1}.

 CAPÍTULO V

MÁQUINAS DE TURING Y

LENGUAJES RECURSIVOS ENUMERABLES

Objetivo:

El alumno conocerá la fundamentación de las máquinas de Turing, sus funciones, los lenguajes que aceptan, su clasificación e Identificará aquellos problemas que no tienen solución computable.

5.1. DEFINICIÓN DE UNA MÁQUINA DE TURING.

El modelo básico, ilustrado en la figura 5.1, tiene un control finito, una cinta de entrada que está dividida en celdas y una cabeza de cinta que barre una celda de la cinta a la vez. La cinta tiene una celda que está más a la izquierda, pero se extiende de manera infinita hacia la derecha. Cada celda de la cinta puede contener exactamente un símbolo de un número infinito de símbolos de la cinta. Inicialmente, las n celdas que están más a la izquierda, para alguna n³ 0 finita, sujetan la entrada, que es una cadena de símbolos escogidos de un subconjunto de los símbolos de la cinta, llamados símbolos de entrada. Cada una del número infinito de celdas restantes sujetan el espacio en blanco, que es un tipo especial de símbolo que no es de entrada.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 5.1 Máquina de Turing.

En un movimiento, dependiendo del símbolo barrido por la cabeza de la cinta y del estado de control finito, la máquina de Turing:

1. Cambia de estado,
2. Imprime un símbolo en la celda de la cinta que está siendo barrida, sustituyendo lo que se encontraba ahí escrito y
3. Mueve su cabeza una celda hacia la izquierda o la derecha.

De manera formal, una máquina de Turing (TM de sus siglas en inglés Turing Machine) se representa por: M=(Q, S , G , d , q0, B, F) en donde:

Q es un conjunto finito de estados.

G es el conjunto finito de símbolos de cinta admisibles.

B símbolo de G , es el espacio en blanco.

S subconjunto de G que no incluye a B, es el conjunto de los símbolos de entrada.

d es la función de movimientos siguiente, una transformación de Q x G a Q x G x {L, R} ( d puede sin embargo, permanecer indefinida por algunos argumentos).

q0 en Q es el estado inicial.

F Í Q es el conjunto de estados finales.

En esta definición se supone que el valor inicial de todas las celdas de la cinta es el símbolo B. La definición requiere que B Ï S . Generalmente permitimos que S Í G – {B}. La función de transición d transforma pares (q, s ) formados por el estado actual y los símbolos de la cinta en ternas de la forma (p, t, x), donde p es el estado siguiente, t es el símbolo escrito en la cinta y x es un movimiento de lectura/escritura de la cabeza, que puede ser L o R, según que el movimiento sea hacia la izquierda o hacia la derecha (nos imaginamos que la cinta se extiende de izquierda a derecha).

Por ejemplo, la transición d (q1, a)=(q5, b, R) provoca que la TM pase de una configuración figura 5.2. A la configuración de la figura 5.3.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura. 5.2 Estado interno q1.Figura. 5.3 Estado interno q1.

Usaremos una descripción instantánea (ID) de la máquina de Turing, para su notación denotando el paso de una configuración a otra por medio del símbolo .

Ejemplo: consideremos la máquina de Turing que acepta el lenguaje regular a*, definida mediante

Q ={q1, q2}

S ={a, b}

G ={a, b, B}

F ={q2}

q0 =q1

y d dada por la siguiente tabla::

los datos de d también se pueden listar de la siguiente manera:

1. d (q1, a) = (q1, a, R)
2. d (q1, B) = (q2, B,R)

Por lo tanto, la ejecución de la máquina de Turing para la cadena "aaa" es la siguiente configuración:

q1aaa por la regla 1 aq1aa, por la regla 1 aaq1a, por la regla 1

aaaq1B, por regla 2 aaaBq2

Esta máquina de Turing para en el estado q2, sólo si se analiza una cadena de cero o más a’s.

Las notaciones * y + tienen el significado usual "cero o más" o "una o más", respectivamente.

Cuando d (q, a) está indefinido y la configuración de la máquina de Turing es imposible que pase a otra se dice que la máquina de Turing está parada. La secuencia de todos los movimientos que conducen a una configuración de parada se llama computación. Para los casos donde la máquina de Turing nunca parará se dice, que la máquina se encuentra en un bucle infinito.

5.2. FUNCIONES DE UNA MÁQUINA DE TURING.

La máquina de Turing puede considerarse como una computadora de funciones que van de los enteros a los enteros. El planteamiento tradicional consiste en representar a los enteros como números unitarios; el entero i³ 0 se representa mediante la cadena 0i. Si una función tiene k argumentos, i1, i2, …, ik, entonces estos enteros se colocan inicialmente en la cinta separados por 1s: 0i1 10i2 … 10ik.

Si la TM se detiene (esté o no en un estado de aceptación) con una cinta que consiste en 0m para alguna m, entonces decimos que ƒ(i1,i2,…,ik)=m, en donde ƒ es la función de k argumentos calculada por esta máquina de Turing.

Adviértase que una TM puede calcular una función de un argumento, una función diferente de dos argumentos y así sucesivamente. Si la TM M calcula la función ƒ de k argumentos, entonces ƒ no necesariamente tiene un valor para cada conjunto diferente de k tuplas de enteros i1,…,ik.

Si ƒ (i1,…,ik) se define para toda i1,…,ik, entonces decimos que ƒ es una función totalmente recursiva. La función ƒ (i1,…,ik) calculada por una máquina de Turing se conoce como función parcialmente recursiva. Las funciones parcialmente recursivas pueden detenerse o no en una entrada dada. Las funciones totalmente recursivas corresponden a los lenguajes recursivos, ya que son calculadas por TMs que siempre se detienen. Todas las funciones aritméticas corrientes sobre los enteros, como la multiplicación, n!, [log2nn] y 22n, son funciones totalmente recursivas.

Ejemplo: La sustracción propia, m n se define como m-n para m³ n y cero para m< n. La TM M=({q0, q1, …, q6}, {0, 1}, {0, 1, B}, d , q0, B, Æ )

que se define más adelante, y que comienza con 0m10n en su cinta, se detiene con 0m n en su cinta. M sustituye de manera repetida su 0 del frente por un espacio en blanco, entonces busca hacia la derecha un 1 seguido por un 0 y cambia el 0 por 1. En seguida M se mueve hacia la izquierda hasta que encuentra un espacio en blanco y entonces repite el ciclo. La repetición termina si:

a) Buscando hacia la derecha un 0, M encuentra un espacio en blanco. Entonces los n 0’s, que están en 0m10n han sido todos cambiados a 1s y n+1 de los m 0’s se han cambiado a B. M sustituye a los n+1 1’s por un 0 y n B’s, dejando m – n 0’s en su cinta.

b) Comenzando el ciclo, M no puede encontrar un 0 que sea cambiado a un espacio en blanco, debido a que los primeros m 0’s ya han sido cambiados. Entonces n ³ m, de modo que m n=0. M sustituye todos los 1’s y 0’s restantes por B.

La función d se descubre a continuación:

Nota: Recuerde que un movimiento de lectura/escritura de la cabeza, puede ser L o R, según que el movimiento sea hacia la izquierda o hacia la derecha, vista en la definición de TM.

1. Comienza. Sustituye el 0 del frente por B.

2. d (q0,0) = (q1,B,R)

   d (q1,1) = (q2,1,R)

   Estructura hacia la derecha, buscando el primer 1.

3. d (q1,0) = (q1,0,R)

   d (q2,0) = (q3,1,L)

   Estructura hacia la derecha saltándose los1s hasta que se encuentra un 0. Cambia ese 0 por 1.

4. d (q2,1) = (q2,1,R)

   d (q3,1) = (q3,1,L)

   d (q3,B) = (q0,B,R)

   Se mueve hacia la izquierda a un espacio en blanco. Accesa el estado q0 para repetir el ciclo.

5. d (q3,0) = (q3,0,L)

   d (q4,1) = (q4,B,L)

   d (q4,0) = (q4,0,L)

   d (q4,B) = (q6,0,R)

   Si en el estado q2 se encuentra una B antes que un 0, tenemos la situación del inciso (a) descrita más arriba. Se accesa el estado q4 y se mueve hacia la izquierda, cambiando todos los 1 por Bs hasta encontrar una B. Esta B se cambia de nuevo a 0, el estado q6 es accesado y M se detiene.

6. d (q2,B) = (q4,B,L)
7. d (q0,1) = (q5,B,R)

d (q5,0) = (q5,B,R)

d (q5,1) = (q5,B,R)

d (q5,B) = (q6,B,R)

Si en el estado q0 se encuentra un 1 en lugar de un 0, el primer bloque de 0s ha sido agotado, como en la situación (b) anterior. M accesa el estado q5 para borrar el resto de la cinta, entonces accesa el estado q6 y se detiene. Una muestra del cálculo de M sobre la entrada 0010 es:

q00010 Bq1010 B0q110 B01q20 B0q311 Bq3011 q3B011 Bq0011 BBq111 BB1q21 BB11q2 BB1q41 BBq41 Bq4 B0q6

Sobre la entrada 0100, M se comporta de la manera siguiente:

q00100 Bq1100 B1q200 Bq3110 q3B110 Bq0110

BBq510 BBBq50 BBBBq5 BBBBBq6

 5.3. LENGUAJES ACEPTADOS POR LAS MÁQUINAS DE TURING.

Una máquina de Turing se puede comportar como un aceptador de un lenguaje. Si colocamos una cadena w en la cinta, situamos la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena w y ponemos en marcha la máquina a partir de su estado inicial. Entonces w es aceptada si, después de una secuencia de movimientos, la máquina de Turing llega a un estado final y para. Por tanto w es aceptada. Si qw * w1pw2 para algún estado final p y unas cadenas w1 y w2. Entonces, se obtiene la siguiente definición:

Sea M = (Q, S , G , q0=q1, B, F, d ) una máquina de Turing. Entonces el lenguaje aceptado por M es: L(M) = {wÎ S *½ q1w * w1pw2 para pÎ F y wiÎ G *}.

Ejemplo. Diseñar una TM que acepte el lenguaje regular a* sobre S ={a, b}. Comenzando con el símbolo que está más a la izquierda en una cadena, realizaremos un análisis hacia la derecha, leyendo cada símbolo y comprobando que es una a; si lo es, realizaremos un desplazamiento hacia la derecha. Si encontramos un blanco (B) sin que se haya leído ningún símbolo que no fuera a, paramos y aceptamos la cadena. Si por el otro lado, encontramos un símbolo que no es ni a ni B, podemos parar en un estado que no es de aceptación.

Sea Q = {q1,q2}, q0=q1 y F={q2}, y sea d definida por:

d (q1,a) = (q1,a,R)

d (q1,B) = (q2,B,R)

Esta máquina de Turing para en el estado q2, sólo si se analiza una cadena de 0 ó más a’s.

Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final. En este ejemplo las cadenas que no son aceptables, provocan que la máquina pare en un estado que no es final. Otra alternativa para rechazar una cadena es entrar en un bucle infinito.

Un lenguaje que es aceptado por una máquina de Turing se conoce como lenguaje recursivamente enumerable (r.e.). El término enumerable proviene de que dichos lenguajes son aquellos cuyas cadenas pueden ser listadas (enumeradas) por una máquina de Turing. Esta clase de lenguajes es bastante grande, incluyendo los lenguajes libres de contexto.

Hay lenguajes r.e. para los cuales ninguna máquina de Turing que los acepte para con todas las entradas (naturalmente, cualquier máquina de Turing para dichos lenguajes debe parar para toda cadena que pertenezca realmente al lenguaje). La subclase de los lenguajes recursivamente enumerables que son aceptados por al menos una máquina de Turing que para con toda cadena de entrada (dependiendo de si la cadena es aceptada o no), se conoce por la clase de los lenguajes recursivos.

Puesto que las máquinas de Turing pueden leer y escribir sobre su cinta pueden convertir la entrada en salida. La transformación de la entrada en salida es el primer propósito de las computadoras digitales; por tanto, una máquina de Turing se considera como un modelo abstracto de una computadora. Se supone que la entrada para la máquina de Turing está formada por todos los símbolos de la cinta que no son blancos. La salida está formada por cualquiera de los símbolos que queden en la cinta cuando la computación termina.

Las máquinas de Turing pueden ser consideradas como la implementación de una función de cadena f definida mediante f(w) = u cuando se cumple qsw * q f u, donde qs es el estado inicial y q f es un estado final, por lo que se requiere que la cabeza de lectura/escritura empiece y termine, respectivamente, sobre el símbolo de las cadenas de entrada y salida que está situado más a la izquierda.

Definiendo lo anterior se dice que una función de cadena f es Turing computable si existe una máquina de Turing M = (Q, S , G , q1,B,F,d ) para la cual q1w * q f u para algún q f Î F, cuando f(w) = u.

Se puede extender la anterior definición de funciones integrales, como se muestra en el siguiente ejemplo.

Ejemplo. Supongamos que tenemos S ={a,b} y que representamos los enteros positivos mediante cadenas de a’s. Así, el entero positivo n estaría representado por an. La función suma f(n,m) = n + m podría ser implementada mediante la transformación de anbam en an+mb. Podríamos obtener una máquina de Turing para la suma, que estaría representada por M = (Q, S , G , q0, B,F,d ), donde

Q = {q1, q2, q3, q4, q5}

q0 = {q5}

y d dada por las siguientes transformaciones:

1. d (q1,a) = (q1,a,R)
2. d (q1,b) = (q2,a,R)
3. d (q2,a) = (q2,a,R)
4. d (q2,B) = (q3,B,L)
5. d (q3,a) = (q4,b,L)
6. d (q4,a) = (q4,a,L)
7. d (q4,B) = (q5,B,R)

Esta máquina de Turing desplaza la b hacia el final, a la derecha de an+m. Para ello se crea una a extra. La máquina de Turing "recordará" que se ha creado una a al pasar al estado q2 una vez que se ha encontrado la b, y entonces se escribirá una b sobre la a que está al final de la cadena. Cuando termina la máquina de Turing la cabeza de lectura/escritura está sobre la a que encuentra más a la izquierda.

5.4. EXTENSIONES DE LAS MÁQUINAS DE TURING

Hay otras definiciones de las máquinas de Turing que son equivalentes. Algunos de esos modelos alternativos son mucho más complicados aunque todos tienen la misma potencia computacional (o de cálculo). Muchas de ellas dotan de mayor flexibilidad al diseño de una máquina de Turing que resuelva un problema en particular. Ejemplos [Kelley Dean]:

Máquina de Turing con Directiva de Permanecer

Recuérdese que la máquina de Turing sencilla sitúa la cabeza de lectura/escritura sobre el primer B que haya a la izquierda de la posición actual. Para hacerlo, busca fuera de la celda actual y retrocede. Esto es debido a la definición original que requiere que por cada transición se mueva la cabeza de la cinta.

La función de transición estaba definida como: d : Q x G ® Q x G x {R, L}

y puede ser modificada como: d : Q x G ® Q x G x {R, L, S} donde S significa "permanecer", es decir no mover la cabeza de lectura/escritura.

Por tanto d (q, s )=(p, s ’, S) significa que se pasa del estado q al p, se escribe s ’ en la celda actual y la cabeza se queda sobre la celda actual.

Máquina de Turing Multipista

Es aquella mediante la cual cada celda de la cinta se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas de la cinta contienen (B, a, a), (b, a, a) y (b, b, B). Por tanto, los movimientos que realice está máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual.

Una máquina de Turing multipista no tiene más potencia que la máquina de Turing original. Sin embargo, hace que sea más fácil la construcción de máquinas de Turing que resuelvan ciertos problemas.

Ejemplo: Para una máquina de Turing que sume dos números binarios. Primero se construye una máquina de Turing de tres pistas. La entrada serán dos números binarios que ocupen las dos pistas superiores de la cinta. Suponiendo que sus dígitos se alinean por la derecha, que sus representaciones binarias son de la misma longitud (lo que se puede conseguir rellenándolas con tantos ceros como sea necesario) y que la cabeza de lectura/escritura se sitúa sobre la celda del extremo izquierdo de la cadena. Por tanto, si tuvieran que sumar 101 y 10, la cinta debería contener

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Cabeza

 La máquina de Turing realizará la suma en la tercera pista. Por tanto, el alfabeto de cinta estará formado por las ternas:

(B, B, B) (1, 1, B) (1, 1, 0) (1, 1, 1)

(0, 0, B) (0, 0, 0) (0, 0, 1) (B, B, 1)

(0, 1, B) (0, 1, 0) (0, 1, 1)

(1, 0, B) (1, 0, 0) (1, 0, 1)

Esta máquina de Turing buscará primero hacia la derecha el extremo derecho de los números que van a ser sumados. Entonces sumará pares de dígitos, desde la derecha hacia la izquierda, llevando la cuenta de los resultados que se obtengan y sumando a quienes corresponda. Por tanto, se obtiene (suponiendo que q1 es el estado inicial):

d (q1, s ) = (q1, s , R), si s ¹ (B, B, B) ó (q2, s , L), si s =(B, B, B)

d (q2, (0, 0, B)) = (q2, (0, 0, 0), L) d (q3, (0, 0, B)) = (q2, (0, 0, 1), L)

d (q2, (0, 1, B)) = (q2, (0, 1, 1), L) d (q3, (0, 1, B)) = (q3, (0, 1, 0), L)

d (q2, (1, 0, B)) = (q2, (1, 0, 1), L) d (q3, (1, 0, B)) = (q3, (1, 0, 0), L)

d (q2, (1, 1, B)) = (q3, (1, 1, 0), L) d (q3, (1, 1, B)) = (q3, (1, 1, 1), L)

d (q2, (B, B, B)) = (q4, (B, B, B), S) d (q3, (B, B, B)) = (q4, (B, B, B), S)

Obsérvese que se necesita que esta máquina de Turing tenga la posibilidad de no moverse. La máquina de Turing transformará

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 en:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Máquina de Turing de Cinta infinita en una Dirección

Máquina de Turing que usa una cinta que se extiende infinitamente en una única dirección. Generalmente, se tiene una cinta que se extiende infinitamente hacia la derecha. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo. Desde luego, cualquier máquina de Turing de esta forma puede ser simulada por una de las que responden a la definición original. Para cada computación, simplemente se marca una de las celdas de la cinta infinita por los dos lados, como la celda que se encuentra en el límite izquierdo.

Máquina de Turing en Dos Direcciones

Una máquina de Turing con una cinta infinita en un sentido puede simular una máquina de Turing con la cinta infinita en los dos sentidos pero con dos pistas. Sea M una máquina de Turing con una cinta infinita en los dos sentidos. La máquina de Turing M’, que tiene una cinta infinita en un sentido, puede simular a M si tiene una cinta con dos pistas. La cinta superior contiene la información correspondiente a la parte derecha de la cinta M, a partir de un punto de referencia dado. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso). Por tanto, si la cinta de M contenía

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Punto de referencia

la cinta de M’ podría ser como

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

El símbolo especial * marca el límite izquierdo de la cinta. Cuando M tuviera que pasar el punto de referencia, M’ tendría que encontrarse con la celda marcada con *. Si M está trabajando sobre las celdas que están a la derecha del punto de referencia, M’ está trabajando sobre la pista superior. Cuando M trabaja sobre las celdas que están a la izquierda del punto de referencia, M’ trabaja sobre la pista inferior. Cuando M pasa al punto de referencia, M’ se encuentra con los *, cambia de dirección y cambia de pista sobre la que trabaja.

Máquina de Turing Multicinta

La máquina de Turing multicinta tiene varias cintas, cada una de las cuales tiene su propia cabeza de lectura/escritura. Las cabezas de lectura/escritura se controlan independientemente (es decir, al mismo tiempo, no tienen que moverse en la misma dirección, ni realizar el mismo número de movimientos, ni incluso, hacer nada a la vez). En un solo movimiento, esta máquina de Turing

1. Cambia de estado dependiendo del estado actual y del contenido de las celdas de todas las cintas, que están analizando actualmente las cabezas de lectura/escritura.
2. Escriben un nuevo símbolo en cada una de las celdas barridas por sus cabezas de lectura/escritura.
3. Mueve cada una de sus cabezas hacia la izquierda o hacia la derecha (de forma independiente al resto de las cabezas).

Por tanto, la función de transición para una máquina de Turing con n cintas, es de la forma d : Q x G n ® Q x G n x {R, L} n donde una transición de la forma d (q, (s 1, s 2,…, s n)) = (p,(t 1, t 2, …, t n), (X1, X2, …, Xn)) significa que cambia del estado q a p, reemplaza s i por t i en la cinta i y mueve la cabeza de la cinta i en la dirección Xi.

Ejemplo: Reconocimiento del lenguaje {anbn |n³ 1}. Éste es bastante laborioso en una máquina de Turing con una única cinta. Es mucho más fácil realizarlo con una máquina de Turing de dos cintas. Suponiendo que, inicialmente, coloca la cadena a analizar en la cinta 1 y que q1 es el estado inicial. Si la cabeza de lectura/escritura de la cinta 1 está situada inicialmente sobre el carácter del extremo izquierdo de la cadena, las cuatro posiciones siguientes son fundamentales para el reconocimiento (cualquier otra transición sería para cadenas mal formadas y se puede suponer que llega a un estado que no es de aceptación):

d (q1, (a, B)) =(q1, (a, a), (R, R))

d (q1, (b, B)) =( q2, (b, B), (S, L))

d ( q2, (b, a)) =( q2, (b, a), (R, L))

d ( q2, (B, B)) =( q3, (B, B), (R, L))

Aunque esta máquina de Turing multicinta parece bastante distinta y posiblemente más potente que la máquina de Turing definida originalmente, las dos son equivalentes en el sentido de que cada una de ellas puede ser simulada por la otra.

Máquina de Turing Muldimensional.

La máquina de Turing multidimensional es aquella que permite que la cinta tenga muchas dimensiones. Por ejemplo, una cinta de dos dimensiones que se extienda hacia abajo y hacia arriba, al igual que hacia la derecha y hacia la izquierda. Dependiendo del estado actual de la máquina de Turing y del símbolo analizado, cambia de estado, escribe un símbolo en la celda actual y se mueve a la izquierda, al derecha, hacia arriaba o hacia abajo. Por tanto, la función de transición para esta máquina de Turing será de la forma:

d : Q x G ® Q x G x {R, L, U, D}

Una máquina de Turing multidimensional simula una máquina de Turing estándar. Simplemente realizando todas sus computaciones en una única dimensión. Una máquina de Turing estándar también puede simular una máquina de Turing multidimensional y, por tanto, la complejidad y la flexibilidad adicional que se debe a la múltiple dimensión, no es una capacidad real. Para simular una máquina de Turing de dos dimensiones mediante una máquina de Turing estándar, primero se asociara una dirección a todas las celdas de la cinta. Una forma de hacerlo es fijar, de forma arbitraria, un lugar en la cinta a partir del cual se asignarán las coordenadas a las celdas de la misma forma que se realiza en un plano de coordenadas.

Entonces, se usara una cinta de dos pistas para simular la máquina de Turing. Una pista se encargará de almacenar el contenido de las celdas y la otra las coordenadas, utilizando un símbolo (*) para separar los valores de las coordenadas. Para simular un movimiento de una máquina de Turing de dos dimensiones, está máquina calcula la dirección de la celda a la que se moverá la máquina de Turing dos dimensiones. Entonces, localiza la pista inferior la celda con dicha dirección y cambia el contenido de la celda en la pista superior.

Máquina de Turing No determinista.

La máquina de Turing No determinista es aquella que para un estado actual y el símbolo actual de la cinta, puede haber un número finito de movimientos a elegir. Por lo tanto, la regla de transición d de dicha máquina, satisface

d (q, s ) Í Q x G x {R, L}

Por ejemplo, si la máquina de Turing tiene una transición

d (q1, a) = {(q1, b, R), (q2, a, L)} entonces los movimientos

abbq1ab abbbq1b y abbq1ab abq2bab son posibles.

Ya que cualquier máquina de Turing determinista es también no determinista, es lógico que una máquina de Turing determinista se puede simular mediante una no determinista. También una máquina de Turing determinista puede simular una no determinista. Por tanto, no se gana ninguna potencia adicional a causa del no determinismo.

5.5. HALTING PROBLEM.

Se dice que un proceso es computable o tiene solución algorítmica cuando puede ser representado por medio de una máquina de Turing que llega, en algún momento, a un estado final.

Si la máquina de Turing llega a un estado final con un sí, se estará haciendo una correspondencia entre ella y el módelo de decisión. Pero cuando la máquina no llega a este estado final pueden suceder dos cosas: que llega a un estado de trampa, de donde ya no salga, o que sencillamente nunca se pueda saber si terminará o no con la computación.

Para el primer caso bastará con hacer una equivalencia entre este estado de trampa y el "no" del modelo de decisión; pero para el segundo hay que decidir entre seguir esperando o no el resultado. En 1936 Turing demostró matemáticamente que existen procesos para los cuales la máquina nunca terminará con un sí y nunca terminará con un no. En este caso se podría esperar toda la eternidad para ver si la máquina se detiene o no, sin poder llegar a saber si se detendrá en el siguiente instante. Se dice que el problema no es computable, o bien, que no es posible decidir, en un tiempo finito, si el proceso es representable algorítmicamente.

Los problemas de este tipo reciben el nombre de problemas indecibles o "problemas no solucionables en forma algorítmica", y representan una prueba de las capacidades del método matemático para explorar la realidad formal del mundo, ya que se está hablando de problemas que son posibles de describir, pero nunca representar por completo para todos los casos.

Turing en la búsqueda de los problemas indecibles generalizó el concepto de máquina, como se explica a continuación:

La máquina universal de Turing es, el módelo teórico de la computabilidad; basta con codificar cualquier máquina particular de Turing en su cinta para que sea entonces simulada y, por ende, pueda resolver ese problema particular algorítmicamente. Y con esto es cuando Turing establece el problema de parada (Halting Problem en inglés) con la siguiente pregunta: ¿Podrá la máquina universal determinar si la máquina – particular – que está siendo simulada se va a detener (en un estado final) o no?

Supóngase que sí puede: que existe una MT1 que determina si cualquier otra (que llamaremos MT0) se va a detener o no; es decir, termina con un sí si MT0 se detiene, y con un no si MT0 no se detiene (véase la figura 5.4). Entonces, también lo podrá hacer para la codificación de sí misma (es decir, podrá determinar si MT1 se detendrá para cualquier caso particular o no).

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 5.4. MT1 termina con un sí, si MTO se detiene ó

termina con un no, si MT0 no se detiene.

Ahora si se construye una nueva máquina, MT2, que se detiene si MT0 no lo hace, y viceversa (véase la figura 5.5). Esto se puede lograr si se hace que MT2 entre en un ciclo infinito cuando MT0 se detiene (mediante un par de estados de trampa, que hacen que la operación de la máquina oscile entre uno y otro).

¿Qué sucede si MT2 trabaja sobre la codificación de sí misma? Pues que se detendrá si MT2 no se detiene, y no se detendrá sí, y sólo sí, se detiene. Esto es una contradicción total. Lo que quiere decir que tal máquina no puede existir; lo que a su vez equivale a decir que el problema que estamos estudiando es indecible.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior 

Figura 5.5. MT2 termina con un sí, si MTO no se detiene

ó termina con un no, si MT0 se detiene.

En resumen, los pasos fueron:

1. Se supone que se puede construir MT1, que determina si MT0 se detiene o no y que, por tanto, también puede determinar si ella misma lo hace, cuando trabaja sobre su propia codificación.
2. Se construye MT2, que termina con un sí, si MT0 no se detiene, y con no si MT0 se detiene mediante un par de estados especiales de atrampa que causan que entre en un ciclo infinito cuando MT0 llega a un estado final.
3. Cuando MT2 trabaja sobre su propia codificación se llega a una contradicción, lo cual significa que la suposición del punto 1 es inválida.

5.6. HIPÓTESIS DE CHURCH.

La hipótesis de que el concepto intuitivo de "función calculable" puede identificarse con la clase de las funciones parcialmente recursivas se conoce como hipótesis de Church. Mientras que no podemos esperar una "demostración" de la hipótesis de Church, puesto que el concepto informal de "calculable" sigue siendo un concepto informal, podemos proporcionar evidencia de su carácter de razonable. Ya que nuestra noción intuitiva de "calculable" no pone un límite en el número de pasos o la cantidad de almacenamiento, parecería que las funciones parcialmente recursivas son intuitivamente calculables, aunque alguien podría argumentar que una función no es "calculable" a menos que podamos limitar el cálculo por adelantado o al menos establecer si el cálculo termina o no en algún momento.

Podemos concluir entonces que la hipótesis de Church es el concepto intuitivo de "Función Calculable" que puede identificarse con la clase de funciones parcialmente recursivas que son las funciones que realiza una máquina de Turing, sin embargo no podemos esperar una demostración de dicha hipótesis, puesto que no se puede definir que es una función calculable porque dejaría de ser intuitiva.

EJERCICIOS.

* Ejercicio resuelto.

*5.1. Diseñe una máquina de Turing que acepte el lenguaje regular a* sobre S ={a, b}, pero que rechace las cadenas que no pertenecen al lenguaje por medio de un bucle infinito.

Q ={q1, q2, q3}, S ={a, b}, G ={a, b, B}, F ={q3}, q0 =q1 y d está definida mediante la siguiente tabla:

Si encuentra una b, la máquina de Turing pasa al estado q2, que se mueve siempre hacia la derecha.

*5.2. Diseñe una máquina de Turing que acepte el lenguaje {0n 1n | n ³ 1}

Q = (q0, q1, q2, q3, q4), S ={0, 1}, G ={0,1,X,Y,B}, F ={q4}, q0 =q0 y donde d está definida mediante la siguiente tabla:

*5.3. Mostrar la ejecución de la máquina de Turing del ejercicio 5.2., cuando se parte de la siguiente configuración: 011, partiendo del estado inicial.

q00011 Xq1011 X0q111 Xq20Y1 q2X0Y1 Xq00Y1 XXq1Y1 XXYq11 XXq2YY Xq2XYY XXq0YY XXYq3Y XXYYq3 XXYYBq4

*5.4. Diseñe una máquina de Turing que complemente las cadenas sobre el alfabeto S ={a, b}.

Q ={q1, q2, q3}, S ={a, b}, G ={a, b, B}, F ={q3}, q0 =q1 y d está definida mediante la siguiente tabla:

*5.5. Diseñe una máquina de Turing que acepte el lenguaje {XÎ {a, b}*½ X contiene la subcadena aba}.

Q ={q1, q2, q3, q4, q5}, S ={a, b}, G ={a, b, B}, F ={q5}, q0 =q1 y la función d , está definida por la siguiente tabla:

*5.6. Diseñe una máquina de Turing que acepte el lenguaje {XÎ {a, b}*½ X termina con aba}.

Q ={q1, q2, q3, q4, q5, q6}, S ={a, b}, G ={a, b, B}, F ={q6}, q0 =q1 y la función d , está definida por la siguiente tabla:

*5.7. Diseñe una máquina de Turing sobre el alfabeto S ={a, b} para la función suma ¦ (n, m) = n + m, representando los enteros positivos mediante cadenas de a’s . Así, el entero positivo n estaría representado por an. La función se implementa mediante la transformación de anbam en an+mb.

Q ={q1, q2, q3, q4, q5 }, S ={a, b}, G ={a, b, B}, F ={q5}, q0 =q1 y la función d , está definida por la siguiente tabla:

Esta máquina de Turing desplaza la b hacia el final a la derecha de an+m. Para ello, se crea una a extra. La máquina de Turing "recordará" que se ha creado una a al pasar al estado q2 una vez que se ha encontrado la b, y entonces se escribirá una b sobre la a que está al final de la cadena. Cuando termina, la máquina de Turing sitúa su cabeza de lectura/escritura sobre la a que se encuentra más a la izquierda.

5.8. Diseñe una máquina de Turing que pare cuando se le presente una cadena del lenguaje {anbm ½ n, m ³ 0 y los dos no son cero a la vez}. Comenzar el procesamiento con la cabeza situada sobre el primer símbolo (el que está más a la izquierda) de la cadena.

9. Diseñar una máquina de Turing para cada uno de los siguientes lenguajes:

1. {a2n ½ n ³ 0} sobre S ={a, b}.
2. {an bn cn ½ n ³ 0} sobre S ={a, b, c}.

5.10. Diseñar una máquina de Turing que acepte el lenguaje {anbn ½ n ³ 0}. Transformar la máquina de Turing para que no pare si encuentra una cadena no aceptable.

5.11. Mostrar la ejecución de la máquina de Turing del ejercicio 5.7., cuando se parte de las siguientes configuraciones: a2ba3 y a2b, partiendo del estado inicial.

5.12. Construir una máquina de Turing de tres pistas que reste el número binario de la segunda pista del número binario de la primera pista y deje el resultado en la tercera pista.

5.13. Diseñe una máquina de Turing para calcular la función n2.

5.14. Construir una máquina de Turing de dos cintas que reconozca el lenguaje {wwI ½ w Î {a, b}+}. Supóngase que, inicialmente, las cadenas a analizar están situadas en la cinta 1.

CAPÍTULO VI

APLICACIONES A LENGUAJES

Objetivo:

El alumno conocerá la relación que existe entre los lenguajes y autómatas y como éstos ayudan en el diseño e implementación de los lenguajes de programación.

6.1. DISEÑO DE LENGUAJES DE PROGRAMACIÓN.

6.2. IMPLEMENTACIÓN DEL COMPILADOR PARA EL LENGUAJE

6.2.2. Implementación de una Gramática Libre de Contexto.

Para ver este capítulo seleccione la opción "Descargar" del menú superior

BIBLIOGRAFÍA

GLOSARIO

ANEXO 1 ALFABETO GRIEGO

ANEXO 2 ABREVIATURAS TÉCNICAS

DEDICATORIAS

Gracias Dios:

Por permitirme gozar el milagro de la vida y darme la oportunidad de ver realizado otro de mis sueños. Siempre albergaste en mí la esperanza de que este día llegaría.

Mil gracias a mis padres Samuel y Martha Laura.

Gracias por apoyarme siempre en todos mis proyectos, por ser un ejemplo de superación que siempre influye en mí en todos los aspectos y sobre todo por compartir conmigo su amor.

Gracias a Alberto, Arturo, Daniel, Angela y Jessica.

Ustedes también contribuyeron al logro de esta meta. Gracias por darme aparte de su amor su apoyo incondicional.

A mis amigos del grupo byte Adriana, Luz María, Esther, Teodora, Aurelio, y Saúl, y especialmente a Kitzya, Graciela, Leobardo y Alfredo por que compartieron conmigo este hermoso sueño que espero no sea el último. Gracias por brindarme su amistad y apoyo.

A mi honorable jurado:

Ing. José Enrique Torres Montoya

M.C. José Hernández Silva

M.E. Ofelia Gutiérrez Giraldi

Lic. Martha Martínez Moreno

Agradezco su colaboración durante la revisión del trabajo. Gracias por sus sugerencias y aportaciones.

A mi asesor, el Ing, José Enrique Torres Montoya.

Siempre agradeceré todo el apoyo que me brindo para hacer de este trabajo una meta alcanzable y lograr mi sueño de ser Ing. En Sistemas Computacionales.

Martha Elizabeth Domínguez Olmos

SECRETARIA DE EDUCACION PUBLICA. DIRECCION GENERAL DE INSTITUTOS TECNOLOGICOS

INSTITUTO TECNOLOGICO DE VERACRUZ