Teor´ıa del Aut´ omata

Dr. Alfonso Alba Cadena [email protected]

Facultad de Ciencias UASLP

Introducci´ on a las notas del curso • Estas notas est´ an dise˜ nadas para ser una gu´ıa en un curso b´ asico de teor´ıa de aut´ omatas y lenguajes formales. El curso inicia con un breve repaso de teor´ıa de conjuntos, y posteriormente presenta los conceptos b´ asicos de aut´ omatas, lenguajes, y gram´ aticas formales, para terminar con la definici´ on de m´ aquinas de Turing, las cuales son una representaci´ on abstracta de lo que es una computadora moderna. ultiples ejercicios, tanto en clase como • Se sugiere realizar m´ en casa, sobre cada uno de los temas revisados, as´ı como implementar simuladores de aut´ omatas y gram´ aticas en un lenguaje de uso com´ un como C/C++. 1

Objetivos Generales • Presentar las m´ aquinas abstractas que forman la base de la teor´ıa de la computaci´ on, y estudiar sus caracter´ısticas y limitantes.

• Estudiar los lenguajes formales y sus propiedades. Mostrar que cualquier problema de c´ omputo equivale al reconocimiento de alg´ un lenguaje.

• Introducir los conceptos b´ asicos de computabilidad y complejidad computacional. 2

Contenido 1. Conceptos b´ asicos de teor´ıa de conjuntos 2. Aut´ omatas finitos y lenguajes racionales aticas y lenguajes 3. Gram´ 4. Aut´ omatas de pila 5. M´ aquinas de Turing 6. Computabilidad y complejidad computacional 3

Bibliograf´ıa sugerida • Teor´ıa de la Computaci´ on: Lenguajes formales, aut´ omatas y complejidad J. Glenn Brookshear Pearson, Addison Wesley Longman

• Automata and Languages John M. Howie Clarendon Press, Oxford

4

Unidad I Conceptos b´ asicos

5

Conjuntos • Definici´ on ingenua: Un conjunto es una agrupaci´ on o colecci´ on de objetos de alg´ un tipo, los cuales pueden o no estar definidos por una o m´ as caracter´ısticas. • Notaci´ on: – Expl´ıcita: se enlistan todos los elementos entre llaves. – Impl´ıcita: se describen las caracter´ısticas que definen los elementos del conjunto. – Ejemplo: {2, 4, 6, . . .} = {x tal que x es entero par positivo}. 6

Notaci´ on • Los conjuntos t´ıpicamente se denotan mediante letras may´ usculas. Ejemplo: A = {a, e, i, o, u},

Φ = {x tal que x2 = 1}.

• Los s´ımbolos ∈ y ∈ / indican pertenencia o no-pertenencia de un elemento en un conjunto. Ejemplo: u ∈ A,

z∈ / A,

−1 ∈ Φ,

3∈ / Φ.

• Los s´ımbolos : y | significan “tal que”. Ejemplo: A = {x : x es vocal min´ uscula},

Φ = {x | x2 = 1}.

• Notar que es posible que un conjunto pertenezca a otro: A = {1, 2}, B = {3, 4, 5} =⇒ {A, B} = {{1, 2}, {3, 4, 5}} .

7

Paradoja de Russell • Esta paradoja surge a partir de la definici´ on ingenua de conjunto. • Sea X un conjunto. Llam´ emosle a X “normal” si X ∈ / X y “anormal” si X ∈ X. • Sea N el conjunto de todos los conjuntos normales; es decir, N = {X | X ∈ / X}. • Es N normal o anormal?. 8

Subconjuntos • Decimos que A es subconjunto de B si y s´ olo si x ∈ A =⇒ x ∈ B (es decir, todo elemento de A es tambi´ en elemento de B). • A es subconjunto propio de B si existe al menos un x ∈ B tal que x ∈ / A; es decir A 6= B. on: A ⊆ B ´ o A ⊂ B (algunos autores utilizan el • Notaci´ s´ımbolo ⊂ para indicar un subconjunto propio) • Notar que: A = B ⇐⇒ A ⊆ B y B ⊆ A. 9

Operaciones con conjuntos • Uni´ on:

A ∪ B = {x | x ∈ A ´ o x ∈ B}

• Intersecci´ on:

• Complemento:

• Resta:

A ∩ B = {x | x ∈ A y x ∈ B} A0 = {x | x ∈ / A}

A − B = {x | x ∈ A y x ∈ / B}

10

Propiedades de las operaciones • Conmutativa:

A ∪ B = B ∪ A, A ∩ B = B ∩ A

• Asociativa Uni´ on:

(A ∪ B) ∪ C = A ∪ (B ∪ C)

• Asociativa Intersecci´ on: • Distributiva Uni´ on:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

• Distributiva Intersecci´ on: • Leyes de DeMorgan:

(A ∩ B) ∩ C = A ∩ (B ∩ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

(A∪B)0 = A0 ∩B 0 y (A∩B)0 = A0 ∪B 0 11

Producto Cartesiano • El producto cartesiano A × B de dos conjuntos A y B se define como el conjunto de todos los pares ordenados en los cuales el primer elemento pertenece a A y el segundo a B: A × B = {(a, b) | a ∈ A y b ∈ B} . • Ejemplo: A B A×B B×A

= = = =

{2, 3} {x, y, z} {(2, x), (2, y), (2, z), (3, x), (3, y), (3, z)} {(x, 2), (x, 3), (y, 2), (y, 3), (z, 2), (z, 3)}

• Notar que A × B 6= B × A. 12

Conjunto vac´ıo • El conjunto vac´ıo es el conjunto ´ unico que no contiene elementos. • El conjunto vac´ıo se denota por ∅ = {}. • Algunas propiedades: / ∅. 1. Para todo x, x ∈ 2. ∅ ∪ A = A, ∅ ∩ A = ∅, A − ∅ = A, ∅ × A = ∅. 3. Para todo x ∈ ∅, x cumple cualquier propiedad. 13

Cardinalidad y conjunto potencia • Un conjunto es finito si tiene un n´ umero finito de elementos; de otra forma, el conjunto es infinito. • El n´ umero de elementos de un conjunto finito A se denomina cardinalidad y se denota por |A|. • Algunas propiedades: |A ∪ B| |A ∩ B| |A ∪ B| |A × B|

≥ ≤ = =

|A| |A| |A| + |B| − |A ∩ B| |A||B| si A y B son finitos 14

Conjunto potencia • El conjunto potencia P(A) de un conjunto A es el conjunto cuyos elementos son todos los subconjuntos de A; es decir: P(A) = {X | X ⊂ A} .

• Ejemplo: si A = {1, 2, 3}, entonces P(A) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} . • Si A es finito, entonces |P(A)| = 2|A|. 15

Relaciones on entre dos conjuntos A y B es un subconjunto • Una relaci´ P de A × B.

un a ∈ A y b ∈ B, entonces decimos que • Si (a, b) ∈ P , para alg´ a est´ a relacionado con b mediante P .

16

Funciones • Una funci´ on φ de un conjunto A a un conjunto B es una relaci´ on de A a B en la que se cumple lo siguiente: Si (a, b1 ) ∈ φ y (a, b2 ) ∈ φ, entonces b1 = b2 . • En otras palabras, una funci´ on asocia a un elemento de A con un ´ unico elemento de B. • Notaci´ on: on φ de A a B se denota como φ : A → B. – Una funci´ – Si (a, b) ∈ φ entonces decimos que b es la imagen de a bajo la funci´ on φ, y esto se escribe como b = φ(a).

17

Dominio e imagen de una funci´ on • El dominio dom φ de una funci´ on φ : A → B se define como dom φ = {a ∈ A | (a, b) ∈ φ para alg´ un b ∈ B} ⊆ A. Si dom φ = A, entonces φ es una funci´ on total, de lo contrario, φ es una funci´ on estrictamente parcial. En general, a cualquier funci´ on se le puede llamar funci´ on parcial. • El contradominio, rango, o imagen im φ de una funci´ on φ se define como im φ = {φ(a) | a ∈ dom φ} ⊆ B. • La funci´ on identidad idA : A → A de un conjunto A se define como idA (a) = a para todo a ∈ A. Notar que dom idA = im idA = A.

18

Tipos de funciones on φ : A → B es uno-a-uno o inyectiva si para todo • Una funci´ a1, a2 ∈ A se cumple que φ(a1) = φ(a2) =⇒ a1 = a2, o equivalentemente a1 6= a2 =⇒ φ(a1) 6= φ(a2). on φ : A → B es sobre o subyectiva si im φ = B; es • Una funci´ decir, para todo b ∈ B existe alg´ un a ∈ A tal que φ(a) = b. • Una funci´ on es biyectiva si es uno-a-uno y sobre. 19

Composici´ on de funciones • Dadas funciones φ : A → B y ψ : B → C, entonces podemos definir la composici´ on ψ ◦ φ : A → B como (ψ ◦ φ)(a) = ψ(φ(a)), para todo a ∈ A tal que φ(a) ∈ dom ψ. • Notar que, en general, φ◦ψ no est´ a bien definido y es distinto de ψ ◦ φ. • Si φ : A → B es una funci´ on, entonces φ ◦ idA = idB ◦ φ = φ. 20

Funci´ on inversa on • Dada φ : A → B, decimos que θ : B → A es una funci´ inversa de φ si θ ◦ φ = idA y φ ◦ θ = idB . on φ es ´ unica y se escribe • Teorema: La inversa de una funci´ como φ−1.

• Teorema: Una funci´ on φ : A → B tiene inversa si y s´ olo si es biyectiva. 21

Cardinalidad • Para un conjunto finito A, su cardinalidad |A| es el n´ umero de elementos que contiene. • Para conjuntos infinitos, el concepto de cardinalidad no es tan claro. Sabemos, por ejemplo, que tanto el conjunto de los n´ umeros naturales positivos N+ como el de los n´ umeros reales R son infinitos, pero intuitivamente uno espera que R tenga un mayor n´ umero de elementos que N+ ya que N+ ⊂ R. • Una forma de mostrar que dos conjuntos tienen la misma cardinalidad es encontrando una funci´ on biyectiva entre ellos. 22

Teoremas sobre cardinalidad • Teorema: Para cualquier conjunto X, |X| < |P(X)|.

• Corolario: |X| < |P(X)| < |P (P(X))| < . . .. Es decir, no existe una cardinalidad m´ axima. • Teorema: Para cualquier conjunto infinito X, |N+| ≤ |X|. Es decir, no existe ning´ un conjunto infinito con cardinalidad menor a la de N+. 23

Conjuntos contables e incontables • Un conjunto X es contable si es finito, o si |X| = |N +|. • Si |X| > |N +|, entonces decimos que X es incontable.

• El conjunto potencia de cualquier conjunto infinito es incontable.

• Si los elementos de un conjunto X se pueden listar de una manera ordenada, entonces el conjunto es contable (ya que existe una funci´ on biyectiva entre X y N+). 24

Ejemplos de conjuntos contables e incontables • N+ × N+ es contable: se pueden enlistar primero las parejas que suman 2, luego las que suman 3, etc.

N+ × N+ = {(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), . . .}. • El conjunto F de funciones de N+ a N+ es incontable ya que |F| ≥ |P(N+)|. Prueba: sea X un subconjunto de N+ , entonces podemos definir la funci´ on fX : N+ → N+ como ½ 1 si x ∈ X fX (x) = 0 si x ∈ / X. Por lo tanto, hay por lo menos tantas funciones como subconjuntos de

N+ . 25

Otro ejemplo • Supongamos que tenemos un lenguaje formado por un conjunto finito de palabras Σ = {w1 , w2 , . . . wn }, donde n = |Σ|. • Un programa equivale entonces a una secuencia de palabras wa1 wa2 . . . waq , donde a1 , a2, . . . , aq ∈ {1, 2, . . . , n}. • La secuencia a1 a2 . . . aq equivale a un n´ umero entero positivo escrito en base n. Esto sugiere un mapeo biyectivo entre el conjunto Σ∗ de todas los posibles programas escritos con palabras de Σ, y el conjunto N+. • Por lo tanto, Σ∗ es contable. Es decir, solamente una cantidad contable de programas se pueden escribir con el lenguaje Σ. • Sin embargo, hay un n´ umero incontable de funciones de N+ a N+ , lo cual significa que para algunas de estas funciones no es posible escribir un programa que las resuelva. 26

Unidad II Aut´ omatas Finitos

27

M´ aquinas abstractas • Para estudiar el alcance y la potencia de c´ omputo de las m´ aquinas actuales, es necesario desarrollar modelos simples de m´ aquinas que tengan las mismas capacidades, pero que sean mas f´ aciles de entender y analizar. • Uno de los modelos m´ as simples (aunque no muy potente) consiste en un sistema en el que nuestra m´ aquina abstracta pueda ubicarse en uno de varios “estados” en un momento determinado. • Adem´ as, la m´ aquina puede recibir datos de entrada, a partir de los cuales decide, seg´ un un conjunto de reglas preestablecidas, si se mantiene en el mismo estado o cambia a un estado distinto. • Estas m´ aquinas abstractas tambi´ en reciben el nombre de aut´ omatas.

28

Diagramas de transiciones • Un diagrama de transiciones es un grafo en el cual los nodos representan los distintos estados de un aut´ omata, y las aristas representan las posibles transiciones entre estados. on de un estado a • Cada arista tiene asociado un s´ımbolo. Una transici´ otro solo se realiza si el dato de entrada coincide con el s´ımbolo de la arista correspondiente. • T´ıpicamente existe un estado inicial (indicado con una flecha), y un estado terminal o de aceptaci´ on indicado con un c´ırculo.

29

Tablas de transiciones • Tambi´ en es posible describir un aut´ omata mediante una tabla de transiciones, como se muestra a continuaci´ on.

⇐⇒

a b

1 2 -

2 4 3

3 4 1

4 1

Estado inicial: 1 Estado final: 4

30

Aut´ omatas finitos deterministas • Formalmente, un aut´ omata finito determinista (AFD) se define como una qu´ıntupla A = (Q, A, φ, i, T ), donde – Q es el conjunto finito de estados del aut´ omata. – A es el alfabeto del aut´ omata; es decir, el conjunto de s´ımbolos que puede recibir como entrada. – φ : Q × A → Q es una funci´ on de transici´ on que asocia a cada pareja (q, a), q ∈ Q, a ∈ A un estado destino φ(q, a). – i ∈ Q es el estado inicial. – T ⊂ Q es el conjunto de estados terminales.

31

Palabras • Dado un alfabeto A una palabra en w en w = a1a2 . . . an donde

(es decir, un conjunto de s´ımbolos), A es una secuencia finita de s´ımbolos a1, a2, . . . , an ∈ A.

• La longitud |w| de una palabra w = a1a2 . . . an es precisamente n. • La palabra vac´ıa es aquella que tiene longitud cero, y se denota com´ unmente como 1 o ² (dado que 1 ∈ /A o ²∈ / A). • Las potencias de una palabra w representan la concatenaci´ on de w con ella misma. Por ejemplo: a3 = aaa, (ab)2 = abab, b(a2 b)3 a = baabaabaaba. 32

Lenguajes • Un lenguaje L sobre un alfabeto A es cualquier conjunto de palabras en A. • El lenguaje que contiene a todas las palabras (finitas) formadas con s´ımbolos de un alfabeto A se denota como A∗. A∗

n

o

= a1a2 . . . an : aj ∈ A para j = 1, . . . , n, y n ∈ N .

• El lenguaje que contiene a todas las palabras en un alfabeto A de longitud positiva se denota por A+. Este lenguaje no contiene a la palabra vac´ıa. A∗ = A+ ∪ {1}. 33

Lenguaje aceptado por un AFD • Notaci´ on: Podemos representar una transici´ on φ(q1, a) = q2 como q1 a = q2 , de manera que es posible escribir algo como: qa1 a2 = (qa1 )a2 = q 0 a2 , si φ(q, a1 ) = q 0 . • Si w = a1 a2 . . . an ∈ A∗ , entonces qw = qa1 a2 . . . an = (((qa1)a2 ) . . .) an . • Dado un AFD A = (Q, A, φ, i, T ) y una palabra w ∈ A, podemos entonces determinar el estado qw al que se llega cuando se ingresa la palabra w al aut´ omata estando en el estado q. • El lenguaje L(A) aceptado por el aut´ omata A se define entonces como L(A) = {w ∈ A∗ : iw ∈ T } . • Un lenguaje L ⊂ A∗ es reconocible por un AFD A si y s´ olo si L = L(A). 34

Ejercicios: 1. Dise˜ nar un diagrama de transiciones para reconocer expresiones aritm´ eticas simples de n´ umeros enteros positivos separados por los s´ımbolos +, −, ×, ÷. Por ejemplo: 54 + 23, 12 − 8, 12345 × 54321, 8 ÷ 3. 2. Dise˜ nar un AFD para una m´ aquina vendedora de refrescos que llegue a un estado de aceptaci´ on cuando el usuario ha introducido la cantidad suficiente para comprar un refresco. Los refrescos cuestan $6 y la m´ aquina acepta monedas de $1, $2, y $5. C´ omo manejar´ıa el caso en el que el usuario introduce m´ as de $6? 3. Dibuje el diagrama de transiciones y describa el lenguaje reconocido por el AFD A = (Q = {q1, q2, q1 }, A = {a, b}, φ, i = q1 , T = {q3 }), donde φ est´ a dada por la siguiente tabla: q1 q2 q3 a q2 q2 q3 b q1 q3 q3 35

L´ımites computacionales de los AFD’s • El lenguaje L = {anbn : n ≥ 1} no es reconocible por ning´ un AFD. • Prueba: Suponer que existe un AFD A = (Q, A, φ, i, T ) tal que L(A) = L. Sea qn = ian para n = 1, 2, . . .. Entonces qnbn ∈ T para todo n. Ya que Q es finito, entonces deben existir m, n distintos tales que qm = qn. Entonces, iambn = qmbn = qnbn ∈ T ; sin embargo ambn ∈ / L, lo cual contradice nuestra suposici´ on inicial. • As´ı como L, existen muchos lenguajes que no pueden reconocerse por ning´ un aut´ omata finito. 36

Lema del bombeo • Sea L un lenguaje infinito reconocible en A∗. Existe entonces un entero positivo N tal que toda z ∈ L con |z| > N puede factorizarse como z = uvw donde 1. u, w ∈ A∗ , v ∈ A+ , 2. |uv| ≤ N , 3. uv m w ∈ L para todo m ≥ 0.

unmente para mostrar (por • El lema del bombeo se utiliza com´ contradicci´ on) que un lenguaje L no es reconocido por ning´ un AFD: uno supone que L es reconocible y elige una palabra z ∈ L y una factorizaci´ on z = uvw adecuadas, de manera que para alg´ un m, uv mw ∈ / L. 37

Ejemplo de uso del Lema del Bombeo • Sea A = {a, b} y L = {w ∈ A∗ : wR = w}, donde wR denota el reverso de una palabra. En otras palabras, L es el lenguaje formado por todos los pal´ındromos en A∗ . • Suponer que L es reconocible por alg´ un AFD. Entonces, existe un N > 0 para el cual se cumple el Lema del Bombeo. • Sea n > N . Considerar la palabra z = an ban ∈ L. Por el Lema del Bombeo, z puede factorizarse como z = uvw con |v| ≥ 1 y |uv| ≤ N < n. Por lo tanto, u = ap , v = aq , y w = ar ban donde q ≥ 1 y p + q + r = n. / L para m 6= 1. Por ejemplo, para m = 0, • Sin embargo, uv m w ∈ uv 0 w = uw = an−q ban ∈ / L. • Por lo tanto, L no es reconocible.

38

Observaci´ on • Teorema: Para cualquier alfabeto A (no vac´ıo), existe una infinidad de lenguajes en A∗ que no son reconocibles. • Prueba: A∗ es infinito contable, por lo tanto, el conjunto de todos los lenguajes en A∗, es decir, P(A∗) es incontable. Por otro lado, el conjunto de todos los AFD cuyo alfabeto es A es contable (se pueden enlistar primero todos los AFD con un estado, luego los que tienen dos estados, etc). Por lo tanto, no existen suficientes AFD para reconocer todos los lenguajes en A∗. 39

Ejercicios 1. Mostrar, usando el Lema del Bombeo, que el lenguaje L = {ap : p es primo} no es reconocible por ning´ un AFD. 2. Sea A = (Q, A, i, T, φ) un AFD. Dise˜ ne otro AFD que reconozca el com∗ plemento de L(A) en A ; es decir, A∗ − L(A). 3. Dise˜ ne un AFD que reconozca n´ umeros, con o sin decimales, positivos o negativos. Por ejemplo, las cadenas 3.1416,

6,

−5.8

son reconocidas, mientras que 3.44.4,

5 − 44. − 4,

.. − −. − . − ..

no lo son. Utilice como alfabeto A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, −, .}.

40

Aut´ omatas Finitos No-Deterministas • Un aut´ omata finito no-determinista (AFN) es una m´ aquina de estado finito en la cual de un mismo estado y con el mismo s´ımbolo de entrada puede haber varias posibles transiciones a distintos estados. • La diferencia con un AFD es que, durante una transici´ on, el estado destino es ´ unico y est´ a bien determinado por la funci´ on de transici´ on. • En el caso de los AFN, la funci´ on de transici´ on no devuelve un solo estado, sino un conjunto de estados destino. 41

Definici´ on formal de un AFN • Un AFN es una qu´ıntupla N = (Q, A, φ, i, T ) donde 1. Q es un conjunto finito no-vac´ıo de estados. 2. A es un alfabeto (conjunto de s´ımbolos finito no-vac´ıo). 3. φ : Q × A → P(Q) es la funci´ on de transici´ on. 4. i ∈ Q es el estado inicial. 5. T ⊆ Q es el conjunto de estados terminales. • De modo que si q ∈ Q y a1 , a2 ∈ A, entonces qa1 es un subconjunto de Q y [ qa1a2 = (qa1 )a2 = pa2 p∈qa1

es tambi´ en subconjunto de Q. • De igual manera se puede obtener el subconjunto qw ⊆ Q, donde q ∈ Q y w ∈ A∗ . 42

²-transiciones • Es posible extender la definici´ on de un AFN para que admita transiciones de un estado a otro sin consumir ning´ un s´ımbolo de entrada. • Este tipo de transiciones se conocen como ²-transiciones (donde ² representa la palabra vac´ıa), de manera que la funci´ on de transici´ on se define como φ : Q × (A ∪ {²}) → P(A). • Es posible mostrar que para todo aut´ omata A que utilice ²-transiciones puede encontrarse un aut´ omata A0 sin ²transiciones tal que L(A0) = L(A). 43

Lenguaje aceptado por un AFN • El lenguaje aceptado por un AFN se define como el conjunto de todas las palabras para las cuales existe una ruta que lleva al aut´ omata del estado inicial a un estado terminal al dar como entrada la palabra.

• Formalmente, si N = (Q, A, φ, i, T ) es un AFN, entonces L(N ) = {w ∈ A∗ : iw ∩ T 6= ∅}.

44

Equivalencia entre AFN’s y AFD’s • Teorema: Sea A = (Q, A, φ, i, T ) un aut´ omata, no necesariamente determinista, y sea L(A) el lenguaje reconocido por A. Entonces existe un aut´ omata determinista completo A0 tal que L(A0) = L(A). • M´ etodo de conversi´ on: Se define el AFD

¡ ¢ A0 = P(Q), A, ψ : P(Q) × A → P(Q), {i}, T 0 = {P ∈ P(Q) : P ∩ T 6= ∅} ,

donde la funci´ on de transici´ on ψ est´ a dada por ψ(P, a) =

[

φ(p, a), para todo P ∈ P(Q), a ∈ A.

p∈P 45

Accesibilidad • En un aut´ omata determinista A = (Q, A, φ, i, T ), un estado q ∈ Q es accesible si existe w ∈ A∗ tal que iw = q; es decir, si es posible llegar a q a partir del estado inicial mediante alguna secuencia de s´ımbolos.

omata A se le dice accesible si todo q ∈ Q es accesible. • Al aut´

• Dado un aut´ omata no accesible A, se puede obtener un aut´ omata accesible A0 tal que L(A0) = L(A) simplemente eliminando los estados no accesibles. 46

Coaccesibilidad • Un estado q de un aut´ omata A = (Q, A, φ, i, T ) es coaccesible si existe w ∈ A∗ tal que qw ∈ T ; es decir, si existe alguna ruta que lleve al aut´ omata de q a alg´ un estado terminal. • Un aut´ omata es coaccesible si todos sus estados son coaccesibles. • Un aut´ omata podado (trim) es aqu´ el que es tanto accesible como coaccesible. • El lenguaje reconocido por un aut´ omata no se modifica si uno elimina todos los estados que no son coaccesibles. 47

Lenguajes racionales • Dados dos lenguajes L1 , L2 ⊆ A∗, definimos la concatenaci´ on o producto L1 L2 como L1 L2 = {uv : : u ∈ L1 , v ∈ L2 }. • Dado un subconjunto L ∈ A∗ definimos L∗ = {u1 u2 . . . un : n ≥ 0, u1 , u2, . . . , un ∈ L}. Esta operaci´ on se conoce como operaci´ on estrella de Kleene. • Un subconjunto de A∗ se llama racional si puede obtenerse a partir de subconjuntos finitos de A∗ mediante un n´ umero finito de operaciones de uni´ on, concatenaci´ on, y estrella de Kleene. • El conjunto de todos los subconjuntos racionales de A∗ se denota por Rat A∗ .

48

Capacidad de reconocimiento de los aut´ omatas finitos • Sea A un alfabeto finito. Cualquier conjunto {w}, w ∈ A∗ (es decir, lenguajes que consistan de una sola palabra) es reconocible. • El conjunto vac´ıo es reconocible. • Sea A un alfabeto finito y sean L1, L2 subconjuntos reconocibles de A∗. Entonces, la uni´ on L1 ∪ L2 es reconocible. • Sea A un alfabeto finito. Entonces, cualquier subconjunto finito de A∗ es reconocible. 49

Teorema de Kleene • Sea A un alfabeto finito y L un subconjunto de A∗. Entonces, L es reconocible si y solo si L es racional.

• La prueba del teorema consiste en mostrar que los lenguajes reconocibles son cerrados bajo las operaciones de uni´ on, concatenaci´ on y estrella de Kleene.

50

Unidad III Gram´ aticas y Lenguajes

51

Gram´ aticas • Una gram´ atica formal o gram´ atica de estructura de frases es una cu´ adrupla Γ = (V, A, π, σ) donde 1. V es un conjunto finito de s´ımbolos llamado vocabulario de Γ. 2. A ⊆ V es el alfabeto terminal. 3. π ⊆ (V − A)+ × V ∗ es el conjunto (finito) de producciones. 4. σ ∈ V − A es el s´ımbolo inicial. • Los elementos de π se llaman producciones y se denotan por u → v, con u ∈ (V − A)+ y v ∈ V ∗ . • Si u → v y u → w, podemos escribir simplemente u → v|w. • La acci´ on de una gram´ atica consiste en generar palabras mediante la sustitici´ on de s´ımbolos no terminales por cadenas de V ∗ . Esta acci´ on termina una vez que la palabra generada contiene solamente s´ımbolos terminales. 52

Lenguaje generado por una gram´ atica • Dada una gram´ atica Γ = (V, A, π, σ), definimos una derivaci´ on w ⇒ w0 para w, w0 ∈ V ∗ si existen x, y ∈ V ∗ y una producci´ on u → v en π tales que w = xuy, w0 = xvy. • En general, si existe una cadena de derivaciones w1 ⇒ w2 ⇒ ... ⇒ wn, podemos escribir simplemente w1∗ ⇒ wn. • De esta manera, se define el lenguaje L(Γ) generado por Γ como el conjunto de palabras en el alfabeto terminal que pueden derivarse del s´ımbolo inicial. Es decir, L(Γ) = {w ∈ A∗ : σ∗ ⇒ w}. 53

Ejemplos de gram´ aticas • Ejemplo 1: Sea Γ = (V, A, π, σ) con A = {el, un, perro, gato, muerde, come}, V = A ∪ {oraci´ on, art´ıculo, sujeto, verbo}, y π consta de las siguientes producciones: oraci´ on art´ıculo sujeto verbo • Ejemplo 2:

→ → → →

art´ıculo sujeto verbo el | un perro | gato muerde | come

Considerar la gram´ atica cuyas producciones son: σ → aσ, σ → bσ, σ → aλ, λ → b.

54

Tipos de gram´ aticas • Las gram´ aticas m´ as simples son las gram´ aticas regulares, en las cuales todas las producciones en π son de la forma α → xβ,

x ∈ A+ , α, β ∈ V − A,

o bien α → y,

α ∈ V − A, y ∈ A∗ .

• Una gram´ atica libre de contexto es aquella cuyas producciones son todas de la forma α → z,

α ∈ V − A, z ∈ V ∗ .

• Un lenguaje es regular (resp. libre de contexto) si puede ser generado por una gram´ atica regular (resp. libre de contexto). • Notar que toda gram´ atica/lenguaje regular es libre de contexto.

55

Lenguajes regulares y racionales • Teorema:

Un lenguaje es regular si y solo si es racional.

• Teorema: Dado un alfabeto finito A y un subconjunto L ⊆ A∗, entonces los siguientes enunciados son equivalentes (es decir, o bien todos son ciertos, o son todos falsos): – L es racional. – Existe un aut´ omata finito A tal que L = L(A). atica regular Γ tal que L = L(Γ). – Existe una gram´ 56

Ejercicios 1. Considere la gram´ atica Γ = (V, A, π, σ) cuyas producciones son: σ → ²|xλ|yγ γ → yγ|² λ → xλ|² a)

Describa el lenguaje generado por Γ.

b)

Dibuje el diagrama de transiciones de un aut´ omata finito que reconozca el mismo lenguaje.

2. Escriba una gram´ atica regular que reconozca el lenguaje L = b2 (ab)∗ a2 . 3. Sean L1 y L2 lenguajes regulares, generados respectivamente por las gram´ aticas Γ1 = (V1 , A1 , φ1 , σ1 ) y Γ2 = (V2 , A2 , φ2 , σ2 ). Construya una gram´ atica regular que genere la concatenaci´ on L1 L2 . 4. Escriba una gram´ atica que genere todos los nombres de variables permitidos en el lenguaje C. 57

Gram´ aticas libres de contexto • Como se vi´ o anteriormente, una gram´ atica libre de contexto (LDC) es aquella en la cual todas las producciones son de la forma α → z,

α ∈ V − A,

z ∈ V ∗.

• Las gram´ aticas LDC son m´ as generales que las regulares, por lo que todo lenguaje racional es libre de contexto.

• Sin embargo, no todo lenguaje libre de contexto es regular. 58

Lenguajes libres de contexto • Ejemplo 1: el lenguaje L = {anbn : n ≥ 1} no es regular, pero es LDC ya que es generado por la siguiente gram´ atica: σ → aλb λ → aλb λ → ² n

• Ejemplo 2: Mostrar que el lenguaje L = w ∈ es libre de contexto, pero no regular.

{a, b}∗

: w=

59

wR

o

Lenguajes libres de contexto • Ejemplo 3: Dado un alfabeto A, si a ∈ A y w ∈ A∗, entonces |w|a denota el n´ umero de ocurrencias de a en w. Verificar que el lenguaje L = {w ∈ {a, b}∗ : |w|a = |w|b} es generado por la siguiente gram´ atica: σ → aµ σ → bλ

λ → a λ → aσ λ → bλ2

µ → b µ → bσ µ → aµ2

60

Forma Normal de Chomsky • Una gram´ atica libre de contexto que genere un lenguaje en A+ se encuentra en la Forma Normal de Chomsky si cada una de sus producciones es de alguno de los siguientes tipos: λ → µν, λ → a,

λ, µ, ν ∈ V − A, λ ∈ V − A, a ∈ A.

Todo lenguaje libre de contexto en A+ puede • Teorema: generarse mediante una gram´ atica en la Forma Normal de Chomsky. 61

Conversi´ on a la Forma Normal de Chomsky 1. Eliminar las producciones del tipo λ → ².

2. Eliminar producciones triviales del tipo λ → µ, µ ∈ V − A. 3. Por cada a ∈ A, agregar un no-terminal βa y reemplazar las ocurrencias de a en todas las producciones por βa. Luego, agregar producciones βa → a para cada a ∈ A. 4. Cambiar cada produccion de la forma λ → α1α2 . . . αn por una cadena de producciones λ → α1λ1, λ1 → α2λ2, . . ., λn−2 → αn−1αn. 62

Ejercicios 1. Para cada uno de los lenguajes siguientes, escribir una gram´ atica libre de contexto que lo genere: (a) L = {ar bsct : s = r + t}. (b) L = {ambnam : m, n ≥ 1}. (c) L = {anbm : 0 ≤ n < m}. 2. Para cada una de las siguientes gram´ aticas, describir el lenguaje que genera y convertirla a la Forma Normal de Chomsky: (a) σ → aσb | cλd, λ → σ | ².

(b) σ → λcµ, λ → aλ | ², µ → bµ | ². 63

Unidad IV Aut´ omatas de pila

64

Limitantes de los aut´ omatas de estado finito • Los aut´ omatas de estado finito realizan una transici´ on hacia un nuevo estado determinado ´ unicamente por el estado actual y el s´ımbolo de entrada, sin importar los estados recorridos anteriormente, o las entradas previas. • Esta incapacidad de recordar estados o entradas previas limita la capacidad de reconocimiento de los aut´ omatas finitos. un tipo de • Para superar esta limitante, podemos agregar alg´ memoria al aut´ omata. Una de las estructuras m´ as b´ asicas de memoria es una pila, en la cual se pueden insertar y extraer s´ımbolos ´ unicamente por un solo extremo de la pila, llamado tope. 65

Aut´ omatas de pila • Un aut´ omata de pila (ADP) es un aut´ omata de estado finito no-determinista al que se le agrega una pila de s´ımbolos y la siguiente funcionalidad: 1. En cada transici´ on, se extrae un s´ımbolo de la pila y se utiliza para decidir a qu´ e estado ir. 2. En cada transici´ on se puede insertar cualquier cantidad de s´ımbolos en la pila. a determinado por: (1) • De esta forma, el estado destino est´ el estado actual, (2) el s´ımbolo de entrada, y (3) el s´ımbolo extra´ıdo del tope de la pila. 66

Definici´ on formal de aut´ omata de pila eptupla M = (Q, A, S, φ, i, ζ, T ), donde • Formalmente, un ADP es una s´ – Q es un conjunto finito de estados – A es el alfabeto del aut´ omata – S es un conjunto finito de s´ımbolos llamado el alfabeto de la pila – φ : Q × (A ∪ {²}) × (S ∪ {²}) → P(Q × S ∗) es la funci´ on de transici´ on. – i es el estado inicial. – ζ ∈ S es el s´ımbolo inicial de la pila. – T ⊆ Q es el conjunto de estados terminales. • La pila del aut´ omata es simplemente una cadena p ∈ S ∗ , la cual se modifica en cada transici´ on. Inicialmente, la pila contiene ´ unicamente al s´ımbolo ζ.

67

Transiciones • La funci´ on de transici´ on se define como φ : Q × (A ∪ {²}) × (S ∪ {²}) → P(Q × S ∗), por lo tanto, podemos definir una transici´ on como una qu´ıntupla de la forma (q, a, α) → (q 0, z),

q, q 0 ∈ Q, a ∈ A ∪ {²}, α ∈ S ∪ {²}, z ∈ S ∗,

si (q 0, z) ∈ φ(q, a, α). Esto significa que, estando en el estado q, con el s´ımbolo de entrada a, y la cadena pα, p ∈ S ∗ en la pila, el aut´ omata puede ir al estado q 0, quedando la cadena pz en la pila (se extrae α y se inserta z). 68

Ejemplo • Considerar el ADP M = ({q0, q1, q2}, {a, b}, {ζ, α}, φ, q0, ζ, {q2}) , donde φ contiene las siguientes transiciones: φ(q0, a, ζ) φ(q0, a, α) φ(q0, b, α) φ(q1, b, α) φ(q1, ², ζ)

= = = = =

{(q0, αζ)}o , n (q0, α2) , {(q1, ²)} , {(q1, ²)} , {(q2, ζ)} .

• Notar que solamente se llega al estado terminal si la cadena de entrada tiene la forma anbn, n ≥ 1. 69

C´ omputos • Una descripci´ on instant´ anea (DI) es una tercia (q, τ, w) donde – q ∈ Q es el estado en el que se encuentra el aut´ omata – τ ∈ S ∗ es el contenido de la pila – w ∈ A∗ es la cadena de s´ımbolos de entrada que a´ un no ha sido le´ıda. • Un c´ omputo en un ADP es una secuencia de DI’s que se obtiene a partir de la aplicaci´ on de una o m´ as transiciones, y puede representarse de la siguiente manera: (q1, τ1, a1a2 . . . an) → (q2, τ2, a2 . . . an) → . . . → (q 0, τ 0, w0). 70

Lenguaje reconocido por un ADP • Sea M = (Q, A, S, φ, i, ζ, T ) un ADP. • Una palabra w ∈ A es reconocida M si existe un c´ omputo de la forma (i, ζ, w) → . . . → (qt, τ, ²),

qt ∈ T, τ ∈ S ∗,

es decir, que lleve al aut´ omata desde el estado inicial a un estado terminal en el cual la secuencia de s´ımbolos de entrada es precisamente w. • El lenguaje L(M) reconocido por M es el conjunto de todas las palabras w ∈ A que son reconocidas por M: L(M) = {w ∈ A∗ : existe un c´ omputo (i, ζ, w) → . . . → (qt , τ, ²), qt ∈ T, τ ∈ S ∗ }. 71

Reconocimiento por pila vac´ıa • Como se mencion´ o anteriormente, una palabra w es reconocida por un aut´ omata de pila M = (Q, A, S, φ, i, ζ, T ) si existe un c´ omputo (i, ζ, w) → . . . → (t, τ, ²),

t ∈ T, τ ∈ S ∗.

• Otra posibilidad consiste en considerar una palabra w como reconocida si y solo si la pila queda vac´ıa una vez que se ha consumido la palabra de entrada; es decir, si y solo si existe un c´ omputo (i, ζ, w) → . . . → (q, ², ²),

q ∈ Q.

Notar que en este caso, ya no es necesario definir un conjunto T ⊆ Q de estados terminales. 72

Equivalencia entre criterios de reconocimiento • Llamemos ADP-ET a los aut´ omatas de pila que reconocen palabras cuando se llega a un estado terminal, y ADP-PV a los que reconocen palabras al vaciarse la pila.

• Se puede demostrar f´ acilmente que los ADP-ET y los ADPPV pueden reconocer la misma clase de lenguajes; es decir, para cada ADP-ET existe un ADP-PV que reconoce el mismo lenguaje, y viceversa.

73

Aut´ omatas de pila y lenguajes libres de contexto • Teorema: Sea A un alfabeto y L ⊆ A∗ . Entonces, L es libre de contexto si y solo si es reconocido por un ADP. • Demostraci´ on (parcial): Suponer que L es LDC, y es generado por una gram´ atica Γ = (V, A, π, σ) en la Forma Normal de Chomsky. Constru´ır el ADP M = ({i, q, t}, A, (V − A) ∪ {ζ}, φ, i, ζ, {t}) , donde φ contiene las transiciones – π(i, ζ, ²) = {(q, ζσ)}, – π(q, λ, ²) ⇒ (q, βα), por cada producci´ on de la forma λ → αβ, – π(q, ζ, ²) = {(t, ζ)}, – π(q, λ, a) ⇒ (q, ²), por cada producci´ on de la forma λ → a. No es dif´ıcil ver que L(M) = L(Γ). 74

Lema del Bombeo para lenguajes LDC • Sea L un lenguaje libre de contexto. Entonces, existe un entero N > 0 que depende ´ unicamente de L, con la propiedad de que si z ∈ L y |z| > N , entonces z puede factorizarse como z = uvwxy de manera que 1. |vx| ≥ 1, 2. |vwx| < N , 3. uv mwxmy ∈ L para todo m ≥ 0. • Ejemplo: mostrar que el lenguaje L = {anbnan : n ≥ 1} no es libre de contexto. 75

Ejemplos de lenguajes no LDC •

n

w2

• {an

2

: w∈

{a, b}+

o

: n ≥ 1}

• {ap : p es primo} •

•

n

n

w∈

{a, b, c}+

wwR w

: w∈

: |w|a = |w|b = |w|c {a, b}∗

o

o

76

Propiedades de cerradura de los lenguajes LDC 1. Si L1 y L2 son LDC, entonces L1 ∪ L2 y L1 L2 tambi´ en lo son. 2. Si L es LDC, entonces L∗ tambi´ en lo es. 3. Si L1 y L2 son LDC, entonces L1 ∩L2 no es necesariamente LDC. Ejemplo: • L1 = {am bm : m ≥ 1} es LDC • L2 = {bn an : n ≥ 1} es LDC • L3 = L1 · a+ = {am bm an : m, n ≥ 1} es LDC • L4 = a+ · L2 = {am bn an : m, n ≥ 1} es LDC • Sin embargo, L3 ∩ L4 = {an bn an } no es LDC. 4. Si L ⊆ A∗ es LDC, entonces A∗ − L no es necesariamente LDC (usar leyes de DeMorgan). 5. Si L1 es regular y L2 es LDC, entonces L1 ∩ L2 es LDC. 77

Ejercicios 1. Para cada uno de los siguientes lenguajes, encontrar un ADP que lo reconozca: (a) {an b2n : n ≥ 1} (b) {ap bp+q aq : p, q ≥ 1} (c) {am bn : m > n ≥ 1} © ª (d) wa|w| : w ∈ {a, b}+ 2. Describir el lenguaje reconocido por el siguiente ADP: (i, a, ζ) (i, b, α) (q, a, α) (q 0 , 1, ζ)

= = = =

{(i, ζα2 )}, {(q, α2 )}, {(q 0 , 1)}, {(t, ζ)}.

(i, a, α) = {(i, α3 )}, (q, b, α) = {(q, α2)}, (q 0 , a, α) = {(q 0 , 1)},

78

Unidad V M´ aquinas de Turing

79

Introducci´ on • Podemos pensar en un aut´ omata (de estado finito o de pila) como una m´ aquina que escanea una palabra w = a1 a2 . . . an impresa en una cinta:

i ↓ a1 a2 . . . an donde la m´ aquina est´ a en el estado inicial i, escaneando el s´ımbolo m´ as a la izquierda. • Tanto los aut´ omatas de estado finito como los aut´ omatas de pila, escanean un s´ımbolo en la cinta, y se mueven a la derecha, posiblemente cambiando de estado (y en el caso de los ADP’s, haciendo posibles ajustes a la pila).

80

Limitantes de los aut´ omatas • Los aut´ omatas de estado finito se ven limitados en los siguientes aspectos: 1. Solamente pueden escanear la cinta hacia la derecha, siendo imposible regresar a escanear s´ımbolos anteriores. 2. Solamente pueden leer el contenido de la cinta, pero no modificarlo. • Los aut´ omatas de pila pueden modificar el contenido de la pila (la cual puede verse tambi´ en como una cinta), pero solamente en un extremo. Tampoco pueden recorrer la cinta m´ as que hacia la derecha. 81

M´ aquinas de Turing • Definici´ on formal: Una m´ aquina de Turing (MT) es una s´ eptupla T = (Q, A, M, ∆, θ, i, T ), donde – Q es un conjunto finito de estados. – A es un alfabeto finito. – M ⊇ A es el conjunto finito de s´ımbolos de la cinta de T . – ∆ ∈ M − A es el s´ımbolo blanco. – i ∈ Q es el estado inicial. – T ⊆ Q es un conjunto no-vac´ıo de estados terminales. – θ es una funci´ on parcial de Q × M a Q × M × {L, R}, donde L y R indican izquierda y derecha, respectivamente.

82

Descripciones instant´ aneas • Una descripci´ on instant´ anea (DI) es una palabra w1qw2, donde w1 ∈ M ∗, w2 ∈ M +, y q ∈ Q, e indica que el contenido de la cinta es w1w2, y que la MT se encuentra en el estado q, escaneando el primer s´ımbolo de w2. • Si w1 = a1a2 . . . am, y w2 = b1b2 . . . bn, entonces la DI w1qw2 puede representarse con el siguiente diagrama: q ↓ a1 a2 . . . am b1 b2 . . . bn

83

C´ omputos • Consideremos la DI w1qw2 , donde w1 = w10 α y w2 = βw20 (con α, β ∈ M ). Entonces, el comportamiento de la m´ aquina de Turing puede ser uno de los siguientes: 1. Si θ(q, β) = (q 0 , β 0 , R), entonces w10 αqβw20 −→ w10 αβ 0 q 0 w20 . 2. Si θ(q, β) = (q 0 , β 0 , L), entonces w10 αqβw20 −→ w10 q 0 αβ 0 w20 . 3. Si q se encuentra cerca del final de la DI y la m´ aquina se mueve hacia la derecha de la cinta, entonces se insertan s´ımbolos blancos conforme sea necesario. Por ejemplo, si θ(q, β) = (q 0 , β 0 , R), entonces w1 qβ −→ w1 β 0 q 0 ∆. • Si dos DI’s pueden conectarse mediante una secuencia de transiciones como las mostradas arriba, entonces a esa secuencia se le llama un c´ omputo en T . 84

Lenguaje reconocido por una MT • Si w ∈ A∗, entonces decimos que w es reconocida por T si existe un c´ omputo iw → . . . → z1tz2, donde i es el estado inicial, t es un estado terminal, z1 ∈ M ∗, y z2 ∈ M + . • El lenguaje L(T ) reconocido por T es el conjunto de todas las palabras w ∈ A∗ reconocidas por T .

85

Ejemplo • Considerar la MT T = (Q, A, M, ∆, θ, i, T ) con Q = {i, q1, q2, q3, q4, t}, M = {a, b, ∆, λ, µ}, A = {a, b}, T = {t}, y θ dada por θ(i, a) θ(q1, a) θ(q1, µ) θ(q2, b) θ(q2, µ) θ(q1, b)

= = = = = =

(q1, λ, R), (q1, a, R), (q2, µ, R), (q3, µ, L), (q3, µ, L), (q3, µ, L),

θ(q3, µ) θ(q3, a) θ(q3, λ) θ(i, µ) θ(q4, µ) θ(q4, ∆)

= = = = = =

(q3, µ, L), (q3, a, L), (i, λ, R), (q4, µ, R), (q4, µ, R), (t, ∆, R).

• Verificar que L(T ) = {anbn : n ≥ 1}.

86

Ejercicios 1. Constru´ır m´ aquinas de Turing que reconozcan los siguientes lenguajes: © ª R ∗ (a) L = ww : w ∈ {a, b} . © ª (b) L = w ∈ {a, b}+ : |w|a = |w|b . (c) L = {an bn an : n ≥ 1}. © ª (d) L = w ∈ {a, b, c}+ : |w|a = |w|b = |w|c . Notar que los lenguajes (c) y (d) no son libres de contexto. 2. Constru´ır una m´ aquina de Turing que reconozca el lenguaje L = {am bn : m es divisor de n}. Sugerencia: por cada a encontrada, cambiarla por λ y luego buscar una b y cambiarla por µ. Una vez que no haya mas a’s, verificar si ya no quedan b’s. En ese caso, aceptar la palabra. De otra manera, cambiar todas las λ’s por a’s y comenzar nuevamente. 87

M´ aquinas de Turing como procesadores de texto • Si consideramos la cinta de una MT como una cadena de caracteres, entonces uno puede considerar la MT como un procesador de texto que realiza alguna tarea espec´ıfica. • Por ejemplo, es relativamente sencillo constru´ır m´ aquinas de Turing que realicen los siguientes procesos: 1. Reemplazar un caracter por otro 2. Reemplazar una secci´ on del texto por otra de la misma longitud 3. Insertar un s´ımbolo, desplazando el texto hacia la derecha 4. Eliminar un s´ımbolo, desplazando el texto siguiente a la izquierda 5. Duplicar una secci´ on del texto 6. Verificar si dos palabras son iguales

88

Clase de lenguajes reconocidos por las MT • Es f´ acil demostrar que cualquier lenguaje regular puede ser reconocido por una MT. • Tambi´ en es posible demostrar que una m´ aquina de Turing no-determinista tiene la misma capacidad de c´ omputo que una MT determinista. • Utilizando lo anterior, es posible demostrar que cualquier lenguaje libre de contexto puede ser reconocido por una MT (determinista o no determinista). • De hecho, la clase de lenguajes que son reconocidos por las m´ aquinas de Turing, son precisamente los lenguajes de estructura de frases; es decir, aquellos que pueden ser generados por una gram´ atica de estructura de frases, donde todas las producciones son de la forma: u → v,

u ∈ (V − A)+ , v ∈ V ∗ .

aquinas de Turing tambi´ en se llaman • Los lenguajes reconocidos por las m´ recursivamente ennumerables. 89

Conjuntos reconocidos por las MT • Utilizando las subrutinas de procesamiento de textos, es posible realizar algunas operaciones relativamente complejas con una MT. Algunos ejemplos son: Operaci´ on

Entrada

Salida

Suma

am∆an∆

am+n∆

Resta

am∆an, n ≤ m

am−n∆

Producto

am∆an∆

amn∆

Divisi´ on

am∆an∆

aq ∆ar ∆, m = nq + r, r < n 90

Ejercicios ne una m´ aquina de Turing que invierta una cadena de • Dise˜ texto.

• Describa, en t´ erminos de subrutinas de procesamiento de textos, c´ omo constru´ır m´ aquinas de Turing que reconozcan los siguientes lenguajes: 2

1. L = {an

: n ≥ 1}

2. L = {ap : p es primo}. 91

Jerarqu´ıa de Chomsky • Sea A un alfabeto finito no vac´ıo, y – F(A∗) el conjunto de todos los lenguajes finitos en A∗, – Rat A∗ el conjunto de todos los lenguajes regulares en A∗, – LDC A∗ el conjunto de todos los lenguajes libres de contexto en A∗, – RE A∗ el conjunto de todos los lenguajes recursivamente ennumerables en A∗, • Entonces, se cumple la siguiente relaci´ on: F(A∗) ⊂ Rat A∗ ⊂ LDC A∗ ⊂ RE A∗ ⊆ P(A∗). 92

Conjuntos que no son reconocidos por las MT • Dado un alfabeto finito no-vac´ıo A, existe una cantidad innumerable de lenguajes en A∗. Esto es debido a que A∗ es infinito contable, y por lo tanto, P(A∗) es infinito incontable. • Por otra parte, el n´ umero de m´ aquinas de Turing que pueden dise˜ narse es contable (pueden enlistarse primero todas las MT con un estado, luego todas las MT con dos estados, etc). • Esto significa que existen lenguajes en A∗ que no pueden ser reconocidos por una m´ aquina de Turing. • Estos lenguajes, sin embargo, no son f´ aciles de encontrar, ya que no pueden ser descritos mediante ning´ un proceso algor´ıtmico.

93

Codificaci´ on de una MT • Supongamos que se desea describir completamente una m´ aquina de Turing T = (Q, A, M, ∆, θ, i, T ) mediante una cadena en {a, b}∗; es decir, mediante una codificaci´ on binaria. • Para hacer esto, podemos ordenar los elementos de Q, T , A, y M − A de una manera conveniente: 1. Q = {q1, q2, . . . , qk , t1, . . . , tl }, con i = q1 y T = {t1, . . . , tl }, 2. A = {a1, . . . , am}, con a1 = a y a2 = b, 3. M − A = {α1, . . . , αn}, con α1 = ∆. 94

Codificaci´ on de una MT • A continuaci´ on, podemos definir las siguientes funciones: – c1(qi ) = ba2i+1 b, para i = 1, . . . , k, – c1(tj ) = ba2j b, para j = 1, . . . , l, – c2(ar ) = ba2r+1 b, para r = 1, . . . , m, – c2(αs ) = ba2s b, para s = 1, . . . , n, – c3(L) = bab, – c3(R) = ba2b. • Definimos tambi´ en la funci´ on c : Q × M × Q × M × {L, R} → {a, b}∗ como: c(q, α, q 0 , α0 , X) = c1(q)bc2 (α)bc1 (q 0 )bc2 (α0 )bc3 (X). • Notar que la funci´ on c codifica una instrucci´ on de la MT en una cadena de a’s y b’s: θ(q, α) = (q 0 , α0 , X) −→ c(q, α, q 0 , α0 , X). 95

Codificaci´ on de una MT • Una MT puede definirse completamente mediante una secuencia finita de instrucciones, por lo que podemos pensar en cualquier MT como un elemento del conjunto (Q × M × Q × M × {L, R})p , p ≤ 1. • Sea K : (Q × M × Q × M × {L, R})+ → {a, b}∗ una funci´ on que mapea una ∗ MT a una palabra en {a, b} definida como: K(z1 , z2, . . . , zp ) = c(z1)b2 c(z2 )b2 . . . b2 c(zp ), donde zi = Q × M × Q × M × {L, R}. • K es una funci´ on uno-a-uno, de manera que a cada m´ aquina de Turing le corresponde una codificaci´ on ´ unica bajo K. Esa codificaci´ on depende del orden en que se enlisten los estados, s´ımbolos, e instrucciones de la MT. on de una MT es una palabra en {a, b}∗, ss impor• Si bien una codificaci´ tante notar que no cualquier palabra en {a, b}∗ corresponde a la codificaci´ on de alguna MT. 96

Un lenguaje no reconocido por ninguna MT on de • Sea A = {a, b}, y W ⊂ A∗ el conjunto de palabras que son codificaci´ una m´ aquina de Turing; es decir, W = {K(z1 , z2 , . . . , zp ) : zi ∈ Q × M × Q × M × {L, R}, i = 1, . . . , p, p ≥ 1} . • Para w ∈ W , sea T (w) la m´ aquina de Turing tal que K(T (w)) = w. • Uno podr´ıa preguntarse si, dada una palabra w ∈ W , la MT T (w) reconoce w. Decimos que w es una buena codificaci´ on si w ∈ L (T (w)) . • Sea G ⊂ W el conjunto de palabras que son buenas codificaciones. • Entonces, el conjunto D = A∗ − G; es decir, el complemento de G en A∗ , no es recursivamente enumerable. • La prueba se realiza por contradicci´ on, suponiendo que D = L(T ) para alguna MT T y verificando si una codificaci´ on w de T es buena o no lo es. 97

M´ aquinas de Turing universales • Una m´ aquina de Turing universal U es una m´ aquina de Turing que toma como entrada una palabra w = w1∆w2 ∈ {a, b}, donde w1 = K(M) es la codificaci´ on de una m´ aquina de Turing M con alfabeto A, y w2 es la codificaci´ on de una palabra en A∗; es decir, w2 = c2(a1 )c2(a2 ) . . . c2 (an ), a1 a2 . . . an ∈ A∗. • La acci´ on de U consiste en simular la acci´ on de la m´ aquina M = T (w1) cuando la entrada de M es a1 a2 . . . an (se puede demostrar que existe una m´ aquina de Turing U es capaz de hacer esto). • Por lo tanto, una m´ aquina de Turing universal es una m´ aquina de Turing que es “programable” cuyo programa se escribe (de manera codificada) en la cinta.

98

M´ aquinas de Turing universales • Consideremos el lenguaje G = {w ∈ {a, b} : w ∈ L (T (w))} ; es decir, el lenguaje que consiste en las codificaciones de todas aquellas m´ aquinas de Turing que aceptan su propia codificaci´ on. aquina de Turing uni• Este lenguaje puede reconocerse mediante una m´ versal que realice los pasos siguientes: 1. Duplicar la palabra en la cinta: w∆ −→ w∆w∆. 2. Codificar la segunda palabra en la cinta: w∆w∆ −→ w∆c2 (a1 )c2 (a2 ) . . . c2 (an )∆, donde w = a1 a2 . . . an . 3. Simular la m´ aquina descrita por w con entrada w. aquina de Turing, • Ya que D = A∗ − G no es reconocible por ninguna m´ entonces es claro que el complemento de un lenguaje recursivamente enumerable no necesariamente es recursivamente enumerable. 99

Lenguajes decidibles • Un lenguaje L ⊂ A∗ es decidible si existe una m´ aquina de Turing capaz ∗ de decidir, para cada w ∈ A , si w pertenece o no a L. • En otras palabras, un lenguaje L ⊂ A∗ si tanto L como A∗ − L son reconocibles por m´ aquinas de Turing. • Todos los lenguajes libres de contexto son decidibles. • El lenguaje G = {w ∈ {a, b} : w ∈ L (T (w))} no es decidible. • Uno puede constru´ır una m´ aquina de Turing que “decida” un lenguaje decidible L haciendo que ´ esta escriba una a al final de la cinta si la palabra de entrada es aceptada, o una b si la palabra no es aceptada.

100

Problema de la parada • Una m´ aquina de Turing T con alfabeto {a, b} es autoterminante si eventualmente se detiene cuando se le da como entrada la palabra K(T ) (independientemente de si la palabra es o no aceptada por la m´ aquina). • Definamos el lenguaje H ⊂ {a, b}∗ como H = {K(T ) : T es autoterminante}. • Consideremos el problema de decidir H. De cierta forma, esto implica decidir si una m´ aquina de Turing se detiene cuando se le da como entrada una cadena espec´ıfica. Debido a esto, al problema de decidir H se le conoce como el problema de la parada. • Puede demostrarse que H no es decidible (suponer que lo es, considerar la MT TH que decide H y modificarla para que entre en un ciclo infinito cuando una palabra es aceptada, preguntarse si esta nueva m´ aquina es autoterminante). 101

Unidad VI Computabilidad y complejidad computacional

102

Computabilidad • Nos interesa ahora el estudio de aquellos procesos que son realizables por una m´ aquina de Turing. • En general, podemos pensar que cualquier tipo de proceso computacional toma una entrada y devuelve una salida correspondiente a dicha entrada. • Por lo tanto, cualquier proceso computacional puede representarse como una funci´ on. • Aunque los dominios y contradominios de las funciones computables pueden ser muy diversos, en general es posible, mediante codificaciones adecuadas, representar cualquier funci´ on computable como una funci´ on parcial de la forma f : Nm → Nn .

103

Funciones iniciales • Es f´ acil ver que las siguientes funciones son computables: – Funci´ on cero: ζ() = 0. – Funci´ on sucesor: σ(x) = x + 1. – Proyecciones: πkm(x1, x2, . . . , xm) = xk .

104

Combinaci´ on y composici´ on • La combinaci´ on de dos funciones f : Nm → Np y g : Nm → Nq es la funci´ on f × g : Nm → Np+q , definida como (f × g)(¯ x) = (f (¯ x), g(¯ x)), es computable si f y g lo son. • La composici´ on de dos funciones f : Nm → Np y g : Np → Nn es la funci´ on g ◦ f : Nm → Nn, definida como (g ◦ f )(¯ x) = g(f (¯ x)), es computable si f y g lo son. 105

Recursividad primitiva on recursiva primitiva h : Nm+1 → Nn se define a • Una funci´ partir de otras dos funciones f : Nm → Nn y g : Nm+n+1 → Nn mediante la siguiente f´ ormula recursiva: h(x, 0) = f (x), h(x, y + 1) = g(x, y, h(x, y)) • Si f y g son computables, entonces h es tambi´ en computable. • Ejemplo: La funci´ on suma sum : N2 → N puede definirse como sum(x, 0) = π11(x), sum(x, y) = (σ ◦ π33)(x, y, sum(x, y)) 106

Funciones recursivas primitivas • Las funciones recursivas primitivas son todas aquellas que pueden constru´ırse a partir de funciones iniciales mediante la aplicaci´ on de un n´ umero finito de combinaciones, composiciones, y recursiones primitivas. • Toda funci´ on recursiva primitiva es computable y total. En otras palabras, si f : Nm → Nn es recursiva primitiva, entonces el dominio de f es Nm. • La mayor´ıa de las funciones que se requieren en procesos de c´ omputo tradicionales son recursivas primitivas. 107

Ejemplos de funciones recursivas primitivas Funci´ on constante: m Kc (¯ x) = c Producto: prod(x, y) = x · y Potencia: Predecesor: Resta no-negativa: ˙ monus(x, y) = x−y Comparaci´ on: x == y

K0m (¯ x) = ζ(), m m Kc (¯ x) = σ(Kc−1 (y)) prod(x, 0) = K01 (x), prod(x, y + 1) = sum(x, prod(x, y)). pot(x, 0) = K11(x), pot(x, y + 1) = prod(x, pot(x, y)). pred(0) = ζ(), pred(y + 1) = π12(y, pred(y)). monus(x, 0) = π11 (x), monus(x, y + 1) = pred(monus(x, y)). eq(x, y) = monus(1, sum(monus(x, y), monus(y, x))). 108

Ejemplos de funciones recursivas primitivas Funciones caracter´ısticas:

κi (x) = eq(x, Ki0).

Negaci´ on l´ ogica:

neg(x) = monus(K10 , x).

Funciones tabulares:

f (x) = Ky01 () · κx1 (x) + Ky02 () · κx2 (x) + ... Ky00 · neg(κx1 (x)) · neg(κx2 (x)).

Cociente:

coc(0, y) = ζ(), coc(x + 1, y) = coc(x, y) + eq(x + 1, (coc(x, y) · y) + y).

109

Funci´ on totales no recursivas primitivas • No toda funci´ on total es recursiva primitiva. Algunos ejemplos son: 1. Es claro que el conjunto F de todas las funciones recursivas primitivas es contable, por lo tanto, pueden enlistarse como P R = {f1 , f2 , . . .}. Considerar la funci´ on f : N → N tal que f (n) = fn (n) + 1. Claramente f es total ya que est´ a bien definida para toda n ∈ N. Sin embargo, se puede probar tambi´ en que f ∈ / P R, y por lo tanto, f no es recursiva primitiva. 2. La funci´ on de Ackermann A : N2 → N se define recursivamente mediante las siguientes ecuaciones: A(0, y) = y + 1, A(x + 1, 0) = A(x, 1), A(x + 1, y + 1) = A(x, A(x + 1, y)). Se puede demostrar que A es computable y total, pero no recursiva primitiva (se demuestra que la funci´ on f (n) = A(n, n) crece m´ as r´ apido con respecto a n que cualquier funci´ on recursiva primitiva). 110

Funciones recursivas parciales • Para obtener una funci´ on parcial f : Nm → Nn (es decir, que no est´ e m necesariamente definida para todo x ¯ ∈ N ), se requiere del operador de minimalizaci´ on µ, cuya acci´ on puede definirse como sigue: f (¯ x) = µy [g(¯ x, y) == 0] , lo cual significa que f (¯ x) es el menor valor de y tal que g(¯ x, y) == 0 y g(¯ x, z) est´ a definida para todo z < y. • Ejemplo: La divisi´ on entera es una funci´ on recursiva parcial que puede definirse como sigue: ˙ div(x, y) = µt [((x + 1)−((t · y) + y)) == 0] . • Si g(¯ x, y) es computable, entonces f (¯ x) = µy [g(¯ x, y) == 0] tambi´ en lo es. • Se puede demostrar que la clase de funciones recursivas parciales es la misma que la clase de funciones computables por una m´ aquina de Turing. 111

Complejidad computacional •

112