t04.2014.modelos de (...).pdf

19/10/2014
4. introducción a los modelos de computación
LENGUAJES
FORMALES
Y
AUTÓMATAS
CONTENIDO
Funciones: propiedades, comparación del
tamaño de conjuntos, cantidad de
introducción
a los modelos
funciones [H2.3], funciones de cifrados,
de computación
1
funciones hash [H2.3], funciones
recursivas [H3.2]. Lógica como modelo de
computación [G1.5]. Lenguajes Formales:
características, descripciones,
operaciones, usos [G8.4]. Conjuntos
contables [H2.4]. Diagonalización [H2.4].
Límites de la computabilidad [H2.4.3].
bibliografía
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
2
HEIN, JAMES. Discrete Structures,
Logic and Computability. Jones and
Bartlett Publishers. 1995 - 2001
propiedades de funciones (repaso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
3
Sea f: A→B una función. Diremos que f
es inyectiva si y sólo si
x,yA x≠y → f(x) ≠ f(y).
Es decir, a elementos distintos del
conjunto de partida le corresponden
elementos distintos del codominio,
GERSTING, JUDITH L. “Mathematical
Structures for Computer Science: A
Modern Approach to Discrete
Mathematics”. W H Freeman & Co,
2006.
propiedades de funciones (repaso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
4
Sea f: A→B una función. Diremos que f
es sobreyectiva si y sólo si
yB x A : f(x) = y.
Es decir, la imagen de f es igual al
codominio de la función.
o lo que
es lo mismo
x,yA f(x) = f(y) → x=y
propiedades de funciones (repaso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
Una función es biyectiva si es inyectiva
y sobreyectiva a la vez.
introducción
a los modelos
de computación
5
propiedades de funciones (repaso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
6
Si f es biyectiva, entonces su inversa f-1
es también una función y además
biyectiva.
Ejemplos:
La función f : R → Z definida como
f(x) = ┌x+1┐
es sobreyectiva porque para cualquier
y  Z existe un número en R, y – 1 tal
que f(y – 1) = y.
Pero f no es inyectiva porque, por
ejemplo, f(2.5) = f(2.6).
1
19/10/2014
propiedades de funciones (repaso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
7
Ejemplos:
La función f : Z → Z definida como
f(x) = x+1
es sobreyectiva porque para cualquier
y  Z existe un número en Z, y – 1 tal
que f(y – 1) = y.
Además f es inyectiva porque, x,yA
x≠y → f(x) ≠ f(y).
Concluimos que f es biyectiva.
La inversa de f, f-1: Z → Z se define
como f-1 (y) = y-1.
propiedades de funciones (repaso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
8
Ejercicios
Cuáles de las siguientes funciones son
inyectivas, sobreyectivas o biyectivas
(si es biyectiva encontrar la inversa):
1. f:N3 →N3 definida como f(x)=2x mod 3.
2. Sea Σ={a,b}
f:Σ* → N definida como f(w)=|w|.
f:Σ* → Z definida como f(w)=|w|.
f:Σ* → Σ* definida como f(w)=aw
la función modulo e inversas
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
9
Lema:
Sea n > 1 y sea f : Nn → Nn definida
como sigue, donde a y b son enteros:
f(x) = (ax + b) mod n.
Entonces f es una biyección si y sólo si
el mcd(a,n)=1. Cuando esto ocurre, la
función inversa f-1 se define como
f-1 (x)=(kx+c) mod n
donde c es un entero tal que f(c)=0 y k
es un entero tal que 1 = ak + nm para
algún entero m.
principio del palomar
Si m palomas vuelan a
un palomar que
contiene n celdas
introducción donde m> n entonces
a los modelos
de computación
una celda tendrá dos
10
o más palomas
LENGUAJES
FORMALES
Y
AUTÓMATAS
Si A y B son conjuntos finitos con |A| > |B|,
entonces toda función de A a B mapea
al menos dos elementos de A a un único
elemento de B. Esto es lo mismo que
decir que no se puede definir una
función inyectiva de A a B.
principio del palomar
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
11
Ejemplos:
1. El juego de la silla, cuando juegan m
personas y quedan m-1 sillas.
2. En un grupo de 8 personas dos
deben haber nacido el mismo día de
la semana.
3. En un conjunto de n+1 enteros
existen (al menos) dos que tendrán el
mismo resto al ser divididos por n.
funciones de cifrado
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
12
Función de cifrado para traducir letras de
un alfabeto, donde cada letra se
codifica con un número del 0 al 26:
f(x)=(x+5) mod 27
La función f “corre” la letra 5 posiciones.
Ejemplo:
Codificamos la palabra hola como mtpf
2
19/10/2014
funciones de cifrado
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
13
Preguntas:
¿Es f una biyección?
¿Cómo decodificamos el mensaje?
f−1(x) = (x – 5) mod 27.
Sabemos f(26)=4
f−1(4) = (4 – 5) mod 27 =(–1) mod 27 =26
criptoanálisis y funciones de cifrado
Criptoanálisis (del griego
kryptós, "escondido" y
analýein, "desatar") es el
introducción estudio de los métodos
a los modelos
de computación para obtener el sentido de
14
una información cifrada,
sin acceso a la información
secreta requerida para
obtener este sentido
normalmente.
LENGUAJES
FORMALES
Y
AUTÓMATAS
fuente: wikipedia
funciones de cifrado
La función f(x)=(x+5) mod 27 es un ejemplo
de función de cifrado aditiva.
Las funciones de cifrado aditivas son
introducción
monoalfabética: un carácter del alfabeto es
a los modelos
de computación
15 siempre reemplazado por un mismo carácter
del alfabeto.
Dado mtpf podemos deducir fácilmente que
codifica la palabra hola.
Otra funciones de cifrado monoalfabéticas son
las funciones de cifrado multiplicativas.
Ejemplo: g(x) = 3x mod 27
¿Es g una biyección?
LENGUAJES
FORMALES
Y
AUTÓMATAS
funciones de cifrado
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
16
funciones de cifrado y puntos fijos
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
17
Lema
Sea n > 1 y sea f : Nn → Nn definida
como sigue donde a y b son enteros
f(x) = (ax + b) mod n.
Entonces f no tiene puntos fijos si y sólo
si mcd(a – 1, n) no divide a b.
Fialka (M-125)
Otro ejemplo de funciones de cifrado
monoalfabéticas son las funciones de
cifrado afines
Utilizan un par de claves: (M,A)
Ejemplo:
clave (4,5)
f(x) =(4x + 5) mod 27.
Pregunta:
¿Cómo desciframos los mensajes?
funciones de cifrado y puntos fijos
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
18
Ejemplo
La función de cifrado
f(x)=(4x + 5) mod 27
no tiene puntos fijos porque:
mcd(4-1,27)=mcd(3,27)=3, y 3 no divide
a5
Por otra parte, la función de cifrado
f(x)=(4x + 6) mod 27
tiene puntos fijos. ¿Cuáles son?
3
19/10/2014
funciones hash
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
19
Una función hash es una función
que mapea un conjunto S de
claves a un conjunto finito de
índices 0, 1, . . . , n – 1 de una
tabla.
funciones hash
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
20
Una tabla cuya información se
encuentra utilizando una función
de hash se denomina tabla hash.
Ejemplo:
Mapear las abreviaturas de los meses
del año utilizando la función de hash f:
S → {0,1,…,11} de la siguiente
manera.
f(XYZ) = (ord(X)+ord(Y)+ord(Z)) mod 12
donde ord(X) el código ASCII de X.
funciones hash
LENGUAJES
FORMALES
Y
AUTÓMATAS
Colisiones:
funciones hash
Preguntas:
¿Es posible encontrar una función inyectiva de
tal manera que no existan colisiones?
introducción
a los modelos ¿Si incrementamos el tamaño de la tabla,
de computación
22
sería más simple encontrar una función
inyectiva?
¿Si el tamaño de la tabla es incrementado,
podemos dispersar los elementos de tal
manera que las colisiones puedan ser
resueltas en menor tiempo?
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
21
¿Cómo asignar un nuevo valor?
Sondeo Lineal:
Buscar hasta encontrar un espacio libre:
(k + 1) mod n, (k + 2) mod n, …, (k + n) mod n.
funciones hash
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
23
Sondeo lineal utilizando huecos (gaps)
Buscar hasta encontrar un espacio libre:
(k + g) mod n,(k + 2g) mod n,...,(k + ng) mod n.
Ejemplos:
Para n = 12 y g = 4
k = 7:
11, 3, 7, 11, 3, 7, 11, 3, 7, 11, 3, 7.
funciones hash
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
24
Aplicaciones de las funciones hash:
Acceso rápido a archivos.
 Identificar archivos (por ejemplo, usado
en sistemas P2P).
 Corroborar que un archivo no haya
cambiado (test de integridad).

Si queremos
encontrar una
biyección
Para n = 12 y g = 5
necesitamos
k=7
mcd(g,n)=1
0, 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7. (1≤g<n)
4
19/10/2014
funciones recursivas sobre naturales
(tema a verse en clase práctica)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
25
Sea suc la función sucesor
suc es tal que suc(x) = x+1.
Definición recursiva de suma
Podemos definir la función suma
recursivamente como sigue:
funciones recursivas sobre naturales
(tema a verse en clase práctica)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
26
Definición recursiva de producto:
prod(n,0) = 0
prod(m, n+1) = suma (m,prod(m, n))
Definición recursiva de exponenciación:
exp(m,0) = 1
exp(m, n+1) = prod(m,exp(m, n))
suma(m,0) = m
suma (m, n+1) = suc (suma (m, n))
Nota: usaremos +,* y ↑ para denotar suma,
producto y exponenciación,
respectivamente.
funciones recursivas sobre naturales
(tema a verse en clase práctica)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
27
Suma de números impares
f(n)=1 + 3 + ··· + (2n + 1)
=(1 + 3 + ··· + (2n − 1)) + (2n + 1)
=(1 + 3 + ··· + 2(n − 1) + 1) + (2n +1)
= f (n − 1) + 2n + 1.
Definición recursiva de f
f (0) = 1,
f (n + 1) = f (n) + 2n + 3.
funciones recursivas sobre naturales
(tema a verse en clase práctica)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
28
Definición recursiva de fibonacci
fib(0) = 0,
fib(1) = 1,
fib(n+2) = fib(n+1) + fib(n)
funciones recursivas sobre cadenas
(tema a verse en clase práctica)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
29
Al trabajar con cadenas, asumiremos
que nuestro alfabeto está compuesto
sólo por los símbolos a y b.
Sea complemento una función definida
sobre cadenas tal que transforma las
a’s en b’s y viceversa.
Definición recursiva de complemento
funciones recursivas sobre listas
(tema a verse en clase práctica)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
30
Notación
L = [] representa la lista vacía
 L = x :: T representa la lista L con
cabeza (primer elemento) x y cola T.
Definición recursiva de longitud

longitud ([] ) = 0
longitud (a::T) = 1 + longitud (T) .
comp(λ) = λ
comp(a.w) = b.comp(w)
comp(b.w) = a.comp(w)
5
19/10/2014
funciones recursivas sobre listas
(tema a verse en clase práctica)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
31
pares([a, b, c], [1, 2, 3]) = [(a, 1), (b, 2),
(c, 3)]
Definición recursiva de pares
lenguajes formales: definiciones básicas
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
32
pares ([ ] ,[ ] ) =[ ] ,
pares (a :: T, b :: T’) = (a, b) :: pares(T,T’) .
gramáticas para lenguajes formales
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
33
Una gramática estructura de frase
(tipo 0) es una 4-tupla
G= (VN, VT, S, P), donde




VN = conjunto de símbolos no terminales.
VT = conjunto de símbolos terminales.
S = símbolo inicial de la gramática.
P = conjunto finito de producciones de la
forma    donde  es una cadena
sobre VN UVT con al menos un símbolo de
VN y  es una cadena sobre VN UVT.
(usamos    cuando  es la cadena
nula)
derivaciones
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
34
derivaciones
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
35
Si w1,w2,...,wn son cadenas sobre VN UVT
y w1  w2, w2  w3,... wn1  wn,
entonces w1 genera (deriva) wn,
+
Se escribe w1  wn
*
(por convención, w1  w1)
Un alfabeto (o vocabulario) Σ es un
conjunto finito no vacío de símbolos.
Una cadena sobre Σ es una secuencia
finita de símbolos de Σ.
Σ* es el conjunto de todas las cadenas
sobre Σ.
Un lenguajes sobre Σ es un
subconjunto de Σ*.
Una gramática para un lenguaje puede
ser descripta definiendo su proceso
generativo.
Sea G=(VN,VT, S, P) y sean w1 y w2
cadenas sobre VN U VT.
Decimos que w1 deriva directamente
w2, y lo notamos w1  w2 si
    es una producción en P,
 w1 contiene una instancia de ,
 w2 es obtenida a partir de w1
reemplazando esa instancia de  con
.
lenguaje formal
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
36
Dada una gramática G, el lenguaje L
generado por G, denotado L(G), es el
conjunto L = {w  VT*| S + w}.
En otras palabras, L es el conjunto de
todas las cadenas de terminales
generadas a partir de S.
Observación: Una vez que una cadena
w de terminales ha sido obtenida,
ninguna producción puede ser aplicada
a w, y w no puede generar otras
palabras.
6
19/10/2014
ejemplo de derivación
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
37
Sea L = {0n1n  n  1}.
Una gramática para L es G=(VN,VT, S,
P) donde VN = {S}, VT = {0, 1}, y P
consiste de las siguientes
producciones:
1. S  0S1
2. S  01
Podemos generar 0313 como sigue:
S  0S1
 00S11
 000111
ejemplo de derivación
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
38
Sea L = {anbncn  n  1}.
Una gramática para L es G=(VN,VT, S,
P) donde VN = {S, B, C}, VT = {a, b, c},
y P consiste de las siguientes
producciones:
1. S  aSBC
2. S  aBC
3. CB  BC
4. aB  ab
5. bB  bb
6. bC  bc
7. cC  cc
ejemplo de derivación
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
39
Podemos generar la cadena a2b2c2
como sigue
S  aSBC
 aaBCBC
 aaBBCC
 aabBCC
 aabbCC
 aabbcC
 aabbcc
clases de gramáticas
LENGUAJES
FORMALES
Y
AUTÓMATAS


introducción
a los modelos
de computación
40


Estructura de frase (tipo 0): sin
restricciones.
Sensible al contexto (tipo 1): para
cada producción  (excepto S ),
|| ≤ | |.
Libre de contexto (tipo 2): para cada
producción  (excepto S),
VN.
Regular (tipo 3) para cada producción
 (excepto S),   VN y  es de
la forma t o tW, donde t  VT y W  VN.
clases de gramáticas
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
41
Ejercicios
Determinar qué lenguaje genera cada
una de las siguientes gramáticas
G=(VN,VT, S, P) . Determinar su tipo.
1)
VN = {S},
VT = 
P: S 
clases de gramáticas
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
42
2)
VN = {S}
VT = 
P=
3)
VN = {S}
VT = {a}
P : S  a | aS
7
19/10/2014
clases de gramáticas
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
43
4)
VN = {S,A},
VT = {a}
P : S   | aA
A  aS
5)
VN = {S},
VT = {a,b}
P : S   | SS | aSb | bSa
clases de gramáticas
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
44
gramáticas y lenguajes
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
45
Un lenguaje se dice de tipo N si puede ser
generado por una gramática de tipo N
tipo 0
tipo1
tipo 2
tipo 3
6)
VN = {S},
VT = {a,b}
P : S  aS
aS  bbb
7)
VN = {S},
VT = {a,b}
P : S  aS
aS  b
dispositivos computacionales
El dispositivo computacional más general se
llama máquina de Turing (se verá en
Teoría de Computabilidad) y se corresponde
introducción
con los lenguajes de tipo 0.
a los modelos
de computación
46 Los lenguajes reconocidos por máquinas de
Turing son los lenguajes de tipo 0.
El dispositivo computacional más básico se
llama autómata finito y se corresponde con
los lenguajes de tipo 3.
LENGUAJES
FORMALES
Y
AUTÓMATAS
Noam Chomsky
(1928-)
Jerarquía de Chomsky
dispositivos computacionales
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
47
Existen dispositivos computacionales
con capacidad intermedia entre
aquellos reconocidos por autómatas
finitos y máquinas de Turing (se verán
en Teoría de Computabilidad):
 Autómatas a Pila para lenguajes de
tipo 2
 Máquinas de Turing acotadas
linealmente para lenguajes de tipo 1.
operaciones sobre lenguajes
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
48
Los lenguajes son conjuntos (finitos o
infinitos) de cadenas y por tal motivo
podemos operar sobre ellos:
Operaciones:
 unión
 intersección
 complemento
 concatenación
 estrella de Kleene
8
19/10/2014
operaciones
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
49
Sean L1 y L2 dos lenguajes sobre un
alfabeto Σ :
L1  L2 = {w | w  L1 ó w  L2}
L1  L2 = {w | w  L1 y w  L2}
L1’ = {w | w  Σ* y w  L1}
L1  L2 = {w1w2 | w1  L1 y w2  L2}
L1* = {w1w2 … wn | wi  L1, n ≥ 0}
operaciones
Ejercicios
Sea Σ = {a,b} y los siguientes lenguajes
definidos sobre Σ
introducción
n n | n > 0} y sea L2 = {bn | n > 0}
a los modelos Sea L1 = {a b
de computación
50
Identificar:
 L1  L2
 L1  L2
 L1’ y L2’
 L1  L2
 L1* y L2*
LENGUAJES
FORMALES
Y
AUTÓMATAS
gramáticas regulares
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
51
Las gramáticas regulares sirven para
generar:
 Cualquier lenguaje finito (aunque
puede volverse una tarea tediosa).
 Lenguajes infinitos que presentan
ciertas regularidades que pueden ser
expresada de manera sencilla
utilizando las llamadas expresiones
regulares (como veremos más
adelante)
gramáticas regulares
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
52
gramáticas libres de contexto
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
53
Las gramáticas libres de contexto tienen
ciertas características destacadas:
Son sencillas, reemplazan un símbolo
por vez.
Pueden ser utilizadas para describir la
sintaxis de los lenguajes de
programación.
La derivación de una gramática libre
de contexto puede ser vista como un
árbol de derivación.
Ejemplos de lenguajes que pueden ser
generados por gramáticas regulares:
 L=. El lenguaje vacío.
 L=Σ*. para cualquier Σ. El lenguaje
universal.
 L={w| w  {a,b}* donde w tiene m a’s
seguidas de n b’s para m,n >0}.
 L={w| w  {0,1}* donde w tiene
exactamente tres 0’s y tres 1’s}.
gramáticas libres de contexto
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
54
Ejemplo de lenguajes que pueden ser
generados por gramáticas libres de
contexto:
 Todos los que pueden ser generados
por gramáticas regulares
 L ={anbn| n > 0}
 L={w|w{(,)}* donde los paréntesis
están balanceados}
 L={w| w {a,b}* y w=wr }.
Observación: Si w = w1w2…wn,
wi {a,b}, entonces wr = wnwn-1…w1
9
19/10/2014
conjuntos contables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
55
Sean A y B conjuntos. Si existe una
biyección entre A y B denotaremos
este hecho escribiendo
|A| = |B|.
En este caso diremos que A y B tienen el
mismo tamaño o la misma cardinalidad
o que son equipotentes.
conjuntos contables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
56
Existe una biyección f:{0, 1, . . . , 13} →A
donde f(x) = (x + 1)3.
Por lo tanto
|A| = |{0, 1, . . ., 13}|= 14.
conjuntos contables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
57
Cardinalidad de un conjunto infinito
Sea Impar el conjunto de números
naturales impares.
Sea f la función f : N → Impar definida
como f(x) = 2x + 1. Dado que f es una
biyección, podemos concluir que el
conjunto Impar y N tienen el mismo
tamaño. Es decir, |Impar| = |N|.
conjuntos contables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
58
conjuntos contables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
59
Propiedades de conjuntos contables
a. Todo subconjunto de N es contable.
b. S es contable si y sólo si |S| ≤ |N|.
c. Cualquier subconjunto de un conjunto
contable es contable.
d. Cualquier imagen de un conjunto
contable es contable.
Cardinalidad de un conjunto finito
¿Cuál es la cardinalidad del conjunto A
definido como sigue?
A = {(x + 1)3 | 1 ≤ (x + 1)3 ≤ 3000, x  N}
Un conjunto se dice contable si es finito
o si existe una biyección entre el
mismo y N. En el último caso se dice
que el conjunto es infinitamente
contable.
En términos de tamaño decimos que un
conjunto S es contable si
|S| = |{0, 1, . . . , n – 1}|
para algún número natural n o |S| = |N|.
Si un conjunto no es contable, decimos
que es incontable.
conjuntos contables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
60
Teorema (Hein página 117-118)
N  N es un conjunto contable.
Prueba:
Se describe una biyección como sigue
(0, 0), ↔ 0,
(0, 1), (1, 0), ↔ 1, 2
(0, 2), (1, 1), (2, 0), ↔ 3, 4, 5,
(0, n), · · · ↔ (n2 + n)/2,· · ·clave: f(x,y) =
((x + y)2 + 3x + y)/2
10
19/10/2014
conjuntos contables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
Teorema (Hein, página 118)
Si S0, S1, …, Sn, … es una secuencia de
conjuntos contables. Entonces la unión
introducción
a los modelos
S0  S1  …  Sn  …
de computación
61
es un conjunto contable.
diagonalización
(se verá al final del curso)
Sea A un alfabeto con dos o más símbolos y sea
S0, S1, …, Sn, … un listado contable de
secuencias de la forma Sn =(an0, an1, …, ann, …),
donde ani A. Las secuencias son listadas como
introducción
las filas de la siguiente matriz infinita
a los modelos
LENGUAJES
FORMALES
Y
AUTÓMATAS
de computación
62
clave: asociar cada tupla (m, n) en N × N con un
elemento xmn en la unión de los conjuntos dados.
Ejemplos de conjuntos contables:
 Los números racionales
 El conjunto Σ* de cadenas sobre un
alfabeto finito Σ.
entonces existe una secuencia S=(a0, a1, …, an,
…) sobre A que no está en la lista original.
diagonalización
(se verá al final del curso)
Podemos construir S a partir de la lista de
elementos diagonales (a00, a11, …, ann, …)
cambiando cada elemento de tal manera que
an≠ ann para cada n. Entonces S difiere de cada
introducción
a los modelos
S0 en el elemento n-ésimo.
de computación
63
Por ejemplo, tomando dos elementos x,y A
definimos
LENGUAJES
FORMALES
Y
AUTÓMATAS
conjuntos incontables
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
64
Ejercicio
Sea (0, 1) = {x  R | 0 < x < 1} y sea R+
el conjunto de reales positivos.
Mostrar que la función f : (0, 1) → R+
definida como
es una biyección.
conjuntos incontables
(se verá al final del curso)
conjuntos incontables
(se verá al final del curso)
Lema (Hein, página 120)
Los números reales son incontables
Prueba
Es suficiente probar que U = (0,1) es incontable.
introducción Asumamos por el absurdo que U es contable.
a los modelos
de computación
Entonces podemos listar todos los números entre 0
65
y 1 como una secuencia contable r0,r1,r 2,… rn, …
Cada número real entre 0 y 1 puede ser
representado como un infinito decimal. Entonces
para cada n existe una representación
rn = 0.dn0dn1. . . dnn. . . , donde cada dni es un dígito
decimal. Dado que rn puede representarse por la
secuencia (0.dn0dn1. . . dnn. . . ), entonces, por
diagonalización podemos concluir que existe un
decimal infinito que no está en la lista (ver Hein).
Concluimos que U es incontable y por lo tanto R es
incontable.
Lema (Hein, página 121)
El conjunto F de funciones de N en N es
incontable
Prueba
introducción
a los modelos
Asumamos por el absurdo que F es contable.
de computación
66
Entonces podemos listar todas las funciones
de N en N como f0,f1,f 2,… fn, …
Cada función fn puede ser representada por
la secuencia de sus valores (fn(0)fn(1). . .
fn(n). . . ), entonces, por diagonalización,
podemos concluir que existe una función
que no está en la lista (ver construcción en
Hein).
Concluimos que F es incontable.
LENGUAJES
FORMALES
Y
AUTÓMATAS
LENGUAJES
FORMALES
Y
AUTÓMATAS
11
19/10/2014
límites de la computabilidad
(se verá al final del curso)
Teorema (Hein, página 122)
El conjunto de programas que pueden ser
escritos utilizando un lenguajes de
programación es infinitamente contable.
introducción
a los modelos
de computación Prueba:
67
Cada programa es una cadena finita de
símbolos sobre un alfabeto finito fijo. Sea Pn
el conjunto de todos los programas que son
cadenas de longitud n sobre A. El conjunto
de todos los programas es la unión de los
conjuntos P0, P1, … , Pn, … Dado que cada
Pn es finito y por lo tanto contable, podemos
concluir que la unión es contable.
LENGUAJES
FORMALES
Y
AUTÓMATAS
límites de la computabilidad
(se verá al final del curso)
LENGUAJES
FORMALES
Y
AUTÓMATAS
introducción
a los modelos
de computación
68
Existe “sólo” un número contable de
programas de computadora. Por lo
tanto existen límites sobre lo que
puede ser computado.
Ejemplos
 Dado que existe un número incontable
de funciones de N → N no todas son
computables. Existen programa para
calcular sólo un conjunto contable de
estas funciones.
límites de la computabilidad
(se verá al final del curso)
Ejemplos (cont.)
 No es posible computar cualquier real hasta
un número arbitrario de cifras decimales. La
razón es que existe un número contable de
introducción
a los modelos
programas y un número incontable de
de computación
69
reales.
 Si extraemos los reales computables de R,
el conjunto restante sigue siendo incontable.
¿Por qué?
 Los números racionales pueden ser
computados.
 Algunos números irracionales pueden ser
computados (ejemplo: π).
LENGUAJES
FORMALES
Y
AUTÓMATAS
12

Download Report