Introducción a la
Informática Teórica
ILI 255
ILI 255
YO: Andrés Moreira
[email protected]
“Investigador Joven”
Oficina F130, VALPO
Horario de Consulta en Stgo: por definir!
ILI 255
Medio habitual de comunicación:
... podría ser
ili255s.blogspot.com
Certámenes:
•20 de abril
•25 de mayo
•29 de junio
Ayudante: Javier Robledo
ILI 255
Bibliografía:
•John Hopcroft et al., Introduction to Automata
Theory, Languages and Computation [2ª ed, 2001]
•Michael Sipser, Introduction to the Theory of
Computation [2ª ed, 2006]
•Juraj Hromkovic, Theoretical Computer Science
[1ª ed, 2003]
 pdfs (y djvu) disponibles
ILI 255
Estarán disponibles además:
•Audio de las clases
•Algunos links y software
•Powerpoint de las clases
-Versión 2010 de los ppts
-Versión “de clase”, light
-Versión “apuntoide”, con más texto
ILI255: Introducción a la
Informática Teórica
AKA: “TALF”
 Teoría de Autómatas
y Lenguajes Formales
“No hay nada más práctico
que una buena teoría”
(K. Lewin)
 Teoría de Autómatas
y Lenguajes Formales
Máquinas
(formales)
Información
(digital)
Preguntas “de fondo”
¿Qué es un computador?
¿Qué puede y qué no puede hacer? ¿Cuánto
tiempo/memoria le cuesta hacerlo?
¿Cómo definimos formalmente un modelo de
computación? ¿Cómo comparamos dos modelos
distintos?
¿Cómo evaluamos la capacidad computacional de un
sistema físico?
¿Cómo caracterizamos la complejidad de la
información?
Temario
0. Repaso lógica, conjuntos, relaciones
1. Strings, lenguajes, operaciones entre lenguajes
2. Lenguajes regulares, autómatas finitos
3. Expresiones regulares (“REGEXP”), aplicaciones,
autómatas deterministas y no-deterministas
4. Minimización de AF
5. Gramáticas formales, jerarquía de Chomsky
6. Lenguajes de libre contexto, autómatas de pila
7. Máquinas de Turing
8. Computabilidad, complejidad computacional
Además (“bonus”)
•En la clase después de almuerzo, en los
primeros 25±5 minutos...
•Transparencia con fondo negro (para evitar
confusiones)...
Además (“bonus”)
•En la clase después de almuerzo, en los
primeros 25±5 minutos...
•Transparencia con fondo negro (para evitar
confusiones)...
Asistencia en ese rato es 100% voluntaria (y
contenido no evaluado). Por cultura general, y
contexto.
 Historia de “la idea de computación”
“La idea de computación” ???
 Algoritmos y máquinas.
Se buscó entender cómo pensamos, y una vez
entendido, reconstruirlo.
Otra forma de decirlo: es la historia de la
formalización del pensamiento abstracto.
“La idea de computación” ???
“formalización del pensamiento abstracto”
Por eso que se entrelazan dos hebras:
- la que llevó a entender las bases y
los límites de las matemáticas
- la que llevó a los computadores y a
la inteligencia artificial
Temario ahí (aproximado)
-Lulio
-Leibniz
-Boole
-Cantor
-Frege
-Hilbert
-Gödel
-Turing
- ... ? (según tiempo)
•Bibliografía: Martin Davis, Engines of Logic
(también disponible como pdf)
¿Qué es un algoritmo?
• A la derecha, don Algoritmo,
o mejor dicho, Muhammad ibn Mūsā alKhwārizmī.
• Escribió un libro en 825…
…que se tradujo en el siglo XII como
"Algoritmi de numero Indorum".
• Eso significaba "al-Khwārizmī hablando
sobre los números hindúes" …
¿Qué es un algoritmo?
… pero se entendió como "Algoritmos
sobre los números hindúes".
• Como el libro se trataba de métodos de
cálculo, se supuso que los tales
"algoritmos" eran esos métodos.
• Y así don "Al-Goritmo" nos hizo dos
aportes: uno queriendo y el otro sin
querer. Ambos importantes.
¿Qué es un algoritmo?
• Es vital en matemáticas tener una
buena notación (fue una virtuosa
obsesión de otros personajes que
vendrán luego, como Leibniz y Boole).
 Las matemáticas jamás podrían haber
avanzado como lo hicieron, si no se
hubiera reemplazado los números
romanos (I,II,III) por los hindúes
(1,2,3). Merci, Muhammad.
¿Qué es un algoritmo?
• Pero además obtuvimos no sólo una
palabra, sino un concepto clave:
algoritmo.
• Tener palabras precisas para conceptos
no triviales, le toma siglos a las
civilizaciones. Merci, traductores malos
del siglo XII.
• Informalmente, un algoritmo es un procedimiento
claramente definido que nos permite resolver un
problema en una cantidad de tiempo finita.
• Formalmente: 8 siglos después (para nosotros, en junio).
Repaso (recordatorio) de algunas cosas
Lógica.
•Trabajamos con expresiones que pueden ser
verdaderas o falsas (V,F), y sus valores de verdad
se combinan de acuerdo a ciertas operaciones.
•El resultado de las operaciones podemos
representarlo mediante tablas de verdad.
•También las tablas pueden servir para demostrar
identidades simples.
NOTA: En informática se suele usar 1 y 0 en lugar
de V y F (respectivamente).
Lógica
Operaciones elementales:
x
y
xy
x
y
xy
x
x
0
0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1
1
Disjunción, “o”
Conjunción, “y”
Negación
Lógica
Algunas propiedades básicas:
•Asociatividad:
(xy)z = x(yz)
,
(xy)z = x(yz)
•Distributividad:
x(yz) = (xy)(xz)
,
x(yz) = (xy)(xz)
•Leyes de Morgan:
(xy) = (x  y)
,
(xy)= x  y
Lógica
Una expresión importante: PQ. La idea es que no se dé
el caso en que P es cierto, pero Q es falso.
Es decir, se quiere la negación de PQ.
Por ley de Morgan, se quiere PQ.
La equivalencia (PQ) se define mediante (PQ 
QP). Uno esperaría que PQ signifique que P y Q valen
lo mismo. En efecto,
PQ QP PQ
P
Q
0
0
1
1
1
0
1
1
0
0
1
0
0
1
0
1
1
1
1
1
Lógica
A partir de una expresión de implicancia PQ
aparecen otras expresiones relacionadas:
•La recíproca: QP
•La contraria: P Q
•La contrarrecíproca: Q P
La recíproca y la contraria son equivalentes entre sí,
mientras que la contrarrecíproca es equivalente a la
expresión original.
Por eso a veces se demuestra Q P, cuando lo
que uno quiere demostrar es PQ.
Lógica
Otra estrategia frecuente es la reducción al
absurdo : uno supone que la conclusión es falsa, y
llega a una contradicción.
Es decir, suponemos que P es cierto y que Q es
falso (es decir, que Q es cierto) y llegamos a
algo falso: PQ = 0, que por ley de Morgan
significa que PQ = 1, o sea, PQ.
Notemos también que si PQ y QR, entonces
PR (ejercicio).
Una consecuencia es que cuando uno quiere
demostrar, por ejemplo, PQRS, basta con
demostrar PQRSP.
Conjuntos
Conjuntos: informalmente, una colección bien definida
de objetos.
“Bien definida”  definición sin ambigüedad
¿“Colección”? ¿”Objetos”?
No es trivial la definición exacta. Sobre todo después
de la intervención de Bertrand Russell, a fines del s.
XIX.
En principio uno tendería a decir que toda propiedad P
define un conjunto: “sean todos los x tales que P(x) es
cierto”.
Conjuntos
Por ejemplo, P(x)=“x es un número primo”.
Entonces el conjunto R(P) será el conjunto de todos los
números naturales primos.
El problema aparece, por ejemplo, con P(x)=“x es un
conjunto que no se incluye a si mismo”.
Pregunta: ¿R(P)R(P)?
Si R(P)R(P), entonces no verifica P, por lo tanto no
debiera estar en R(P)  R(P)R(P)
Pero si R(P)R(P), entonces verifica P, y por lo tanto sí
debiera estar en R(P)  R(P)R(P)
Conjuntos
Es la “paradoja de Russell”. ¿Por qué surge?
•R(P) es un conjunto de conjuntos. Eso no es pecado;
cuando uno toma (por ejemplo) “todos los
subconjuntos de {0,1,2,3}”, hace justamente eso.
•El problema sí surge del hecho de que no hemos
definido el universo de objetos que estamos
considerando. Es demasiado vago!!
•Solución: varias.
Conjuntos
La más popular: usar los axiomas de Zermelo-Frankel
para definir lo que es un conjunto (y el monstruo de la
paradoja nunca aparece).
Definir conjuntos a través de propiedades sí
funciona, pero restringiéndose a objetos que estén
en algún conjunto previamente construido (como el
ejemplo de los primos).
Sin embargo la paradoja (o el poder) de la auto-referencia
volverá a aparecer en el curso.
“Los cretenses siempre mienten.”
Epiménides (un cretense)
Conjuntos
•Para evitar paradojas, y tener punto de referencia, se
suele trabajar dentro de un conjunto, el “universo” o
“conjunto universal” U.
•Se define el complemento con respecto a ese U:
AC = {xU: xA}
•Todo conjunto admite el subconjunto vacío, . El
conjunto vacío es único.
•El conjunto potencia de un conjunto A, es el conjunto
P(A) formado por todos sus subconjuntos.
•Si |A|=n, entonces |P(A)|=2n.
•Si A  B, entonces P(A)  P(B).
Conjuntos
Inclusión de la intersección:
ABAyABB
Inclusión en la unión:
AAByBAB
Transitividad de la inclusión:
(A  B  B  C)  A  C
Conjuntos vs Lógica:
xXYxXyY
xXYxXyY
x  X\Y  x  X  y  Y
x  Xc  x  X
Conjuntos
Conmutatividad:
AB=AB
y
AB=BA
Asociatividad:
(A  B)  C = A  (B  C) y
(A  B)  C = A  (B  C)
Distributividad:
A  (B  C) = (A  B)  (A  C) y
A  (B  C) = (A  B)  (A  C)
Conjuntos
Intersección y unión con conjunto universal:
AU=A y AU=U
Doble complemento:
(Ac)c = A
Idempotencia:
AA=A y AA=A
De Morgan:
(A  B)c = Ac  Bc y (A  B)c = Ac  Bc
Absorción:
A  (A  B) = A and A  (A  B) = A
Conjuntos
Sean A, B subconjuntos de U. Entonces las
afirmaciones siguientes son equivalentes:
a)
b)
c)
d)
AB
AB=B
AB=A
BCAC
U
Demostración: ejercicio. Aplicar eso de
demostrar a  b  c  d  a.
Diferencia simétrica: A  B=A\B  B\A
Ejercicio: demostrar que es asociativa.
B
A
Repaso
1. Lógica
2. Conjuntos
3. Inducción
4. Relaciones
5. Clases de equivalencia
6. Cardinales
Conjuntos
Un par de conjuntos se dicen disjuntos si su
intersección es vacía (no tienen elementos en común).
Nótese que A\B y B son siempre disjuntos.
Una colección {A1,…Ak} se dice mutuamente disjunta si
cualquier par de conjuntos de la colección es disjunto.
Una colección de conjuntos no vacíos {A1,…Ak} es una
partición del conjunto A si se cumple
(1) {A1,…Ak} es mutuamente disjunta
(2) A es igual a la unión de todos los Ai
Si sólo se cumple lo segundo, decimos que es un
recubrimiento de A.
Inducción
Recordar el principio de inducción:
Se usa para demostrar que una proposición P que
depende de un número natural “n”, es decir, P(n), es
cierta para todo “n” por sobre algún umbral n0.
Lo que se hace es demostrar:
•Que P(n0) es cierta [“caso base”]
•Que si P(n) es cierta (para cualquier n ≥ n0),
entonces P(n+1) también es cierta [“paso inductivo”]
En una variante, que a veces se llama inducción
“fuerte”, el paso inductivo demuestra que si P(k) es
cierta para todo n0 ≤ k ≤ n, entonces lo es para n+1.
Inducción
Un ejemplo clásico:
n
i 
n ( n  1)
2
i 1
Caso base:
n  1
1
1(1  1)
i 1
2
i  1 
Paso inductivo:
n 1
n
n( n  1)
i 1
i 1
2
 i  (n  1)   i  (n  1) 

2( n  1)  n( n  1)
2

( n  2)( n  1)
2
Inducción
Otros:
•n3-n es divisible por 3, para todo n ≥ 1
•2x ≥ x2, para todo x ≥ 4
•… etc (pueden mirar su cuaderno de aquellos tiempos;
lo importante es que refresquen estas cosas).
Un poco menos trillado: inducción “estructural”:
•Generaliza la misma idea.
•La usamos para demostrar propiedades de objetos
definidos recursivamente.
Inducción estructural
En una construcción recursiva, se tienen:
•Objetos básicos (“primitivos”, “iniciales”, etc..)
•Reglas para definir nuevos objetos a partir de un
conjunto de objetos ya definidos.
Entonces se demuestra que la propiedad en cuestión (el
“predicado”):
•Es cierta para los objetos básicos
•Si es cierta para un conjunto de objetos, entonces
es cierta para el nuevo objeto construido, mediante
las reglas, a partir de dicho conjunto.
Inducción estructural
Ejemplo clásico: consideremos la siguiente definición
recursiva de un árbol [conexo].
•Un nodo sólo, es un árbol.
•Si T1, T2, …, Tk son árboles disjuntos, entonces
n
A
T1
A
T2
también es un árbol.
...
A
Tk
Inducción estructural
Propiedad a demostrar: la cantidad de nodos siempre
es igual a la cantidad de aristas + 1.
•Caso base: ok.
•Sean ni y ai las cantidades de nodos y aristas en los
árboles Ti, para i de 1 hasta k. Sean n y a esas
cantidades para el nuevo árbol.
Hipótesis inductiva: ni  ai  1 i
n
Paso inductivo:
k
k
n  1   ni  1   ( ai  1)
i 1
k
i 1
 1  k   ai  1  a
i 1
A
T1
...
A
T2 ...
A
Tk
Inducción estructural
Otro ejemplo típico: expresiones aritméticas.
Símbolos elementales: letras, +, *, (, )
(1) Las letras son E.A.
(2) Si E y F son E.A., entonces E+F, E*F y (E) son
E.A.
Ejemplos: x+y, x*y+x*(z+b), ((a)), etc…
Ejercicio: demostrar que en una expresión aritmética,
el número de “(“ es igual al número de “)”.
Inducción estructural
Números de Fibonacci:
•
•
F(1)=F(2)=1,
F(n)=F(n-1)+F(n-2) para n > 2
Demostrar que F(n) < 2n para todo n ≥ 1
Nótese que en este caso lo podemos ver como inducción
“clásica”, o bien como inducción estructural.
Tuplas y producto cartesiano
•Una n-tupla ordenada es una secuencia de n
elementos, escrita en la forma (x1,…,xn).
•Nótese que a diferencia de los conjuntos, donde
{1,2}={2,1}, en una n-tupla el orden sí importa.
•Por lo tanto, la única forma de que (x1,…,xn)=
(y1,…,yn) es que x1=y1,…,xn=yn.
•El producto cartesiano de n conjuntos A1,...,An es el
conjunto formado por las n-tuplas de la forma
(x1,…,xn), donde xiAi, 1 ≤ i ≤ n :
A1  A2    An  {( x1 ,, xn ) : xi  Ai1  i  n}
Relaciones
Un caso de particular interés es el producto
cartesiano de sólo dos conjuntos: AB.
Una “relación” es un subconjunto RAB.
Nótese que:
•no necesariamente A=B
•cualquier subconjunto RAB es válido
Con A={1,2,3},B={,}, las siguientes
son todas relaciones válidas:
R2 

R1={(1,),(1,),(3,)}
R2=AB \ {(1,)}
R3={(2,)}
1
2
3
1
2
3
R3 
R1 


1
2
3
Relaciones: funciones
Un caso aún más particular son las funciones: son
relaciones en que para cada xA, existe un único yB
tal que (x,y)R; así, se define una función de A en B.
Las tres relaciones en la
transparencia anterior son
contraejemplos : no son funciones.
En cambio, R4 (a la derecha) sí lo es.
R5 

1
2
3
R4 

1
2
3
¿Qué hay de R5, a la izquierda? No es una
función, porque estamos viéndolas como
subconjuntos de AB. Pero en este caso si la
“trasponemos”, y la vemos como subconjunto de
BA, entonces sí es una función... de B en A.
Relaciones: notación
•Cuando una relación RAB es una función, y se
tiene (x,y)R, solemos escribir R(x)=y. Por ejemplo,
R4(1)=.
•En el caso general (en que R es una relación
cualquiera), cuando (x,y)R se suele escribir xRy.
NOTA: En lo que sigue, consideraremos relaciones
dentro de un mismo conjunto: A=B, y le llamaremos
“S” (o sea, A=B=S). Anotamos S2=SS.
Relaciones: propiedades
Decimos que una relación RS2 es:
•Refleja: si para todo aS, (a,a)R [o sea, aRa].
•Transitiva: si cada vez que aRb y bRc, se tiene
además aRc.
•Simétrica: si aRb  bRa
•Antisimétrica: si cada vez que aRb y bRa,
necesariamente a=b.
•Total: para cualesquiera a,bS, se tiene que
aRb o bien bRa (o ambas).
Relaciones: orden
Una relación de orden parcial cumple con ser
refleja, transitiva y antisimétrica.
•Ejemplo: Sea A un conjunto finito, S=P(A) [el
conjunto potencia de A], y R definida por
R = { (B,C): B,CA y BC }
(es decir: es la relación de inclusión entre
subconjuntos de A).
NOTA: esto es lo que se llama un orden “no estricto”.
En los órdenes estrictos, como “<“ y “”, se prohibe la
igualdad, exigiendo que la relación sea antirrefleja:
(a,a)R para ningún a.
Relaciones: orden
Si además es total, entonces es una relación de
orden total.
•El ejemplo anterior es un caso de orden parcial que
no es total. Para ver por qué, consideremos A={1,2},
B={1}, C={2}. Claramente, ni B está incluído en C, ni C
está incluído en B.
•Consideremos S=Z (los números enteros), y la
relación  habitual. Ese sí es un caso de relación de
orden total.
Relaciones: equivalencia
Una relación de equivalencia cumple con ser refleja,
transitiva y simétrica.
•Ejemplo: Sean Z los números enteros, y sea mN,
m0. Definiremos la relación Rm (pues ojo, depende
del m) como
a Rm b  a mod m = b mod m
[donde a mod m es el resto de dividir a por m]
Ejercicio:
1) ver que es relación de equivalencia
2) ver que a Rm b  (a-b) es divisible por m.
Relaciones: equivalencia
Sea R una relación de equivalencia en S.
• Para cada elemento aS, definimos su clase de
equivalencia [a]={ bS: aRb }.
• El conjunto de las clases de equivalencia forma
una partición de S. En efecto:
•Todo elemento pertenece a alguna clase de equivalencia
(la suya!).
•La intersección entre dos clases de equivalencia distintas
es vacía: si c[a][b]  c[a] y c[b]  cRa y cRb 
aRc y cRb (por simetría)  aRb (por transitividad) 
[a]=[b].
Relaciones: equivalencia
•Ejemplo: consideremos (Z,R3), con la relación de
“igualdad módulo 3” definida antes. Entonces
[0] = { ..., -6, -3, 0, 3, 6, 9,... }
[1] = { ..., -5, -2, 1, 4, 7, ... }
[2] = { ..., -4, -1, 2, 5, 8, 10, ... }
Al conjunto de clases de equivalencia (conjunto
“cuociente”) lo anotamos S/R. En este caso,
Z/R3 = { [0], [1], [2] }
Naturalmente, en un mismo conjunto puede
definirse más de una relación de equivalencia, y
cada una dará una partición distinta.
Relaciones: equivalencia
•Ejemplo: Sea S una baraja de naipe [inglés],
S={ 1, 2, ..., K, 1, 2, ..., K,
1, 2,..., K, 1, 2, ..., K}
y consideremos las relaciones
Rp : si dos naipes son de la misma pinta
Rn : si dos naipes son del mismo número
Rc : si dos naipes son del mismo color
R2 : si el número de dos naipes tiene la misma paridad.
¿Cuántas clases de equivalencia distintas hay en cada
caso?
Relaciones: refinamientos
Nota: La relación entre relaciones de equivalencia y
particiones es recíproca: dada una partición de un conjunto,
podemos definir una relación de equivalencia (según si los
elementos quedan juntos o no).
Sean R,QS2 dos relaciones de equivalencia en S.
Decimos que R es más fina que Q, y escribiremos
RQ, si se tiene
aRb  aQb, a,bS
Es decir, R distingue entre elementos de S al menos
tan bien como Q. Ejercicio: demostrar que si RQ,
entonces las clases de equivalencia de Q son
uniones de clases de equivalencia de R.
Relaciones
•En el ejemplo de los naipes, RpRc , y RnR2.
•Si consideramos la relación de igualdad módulo m,
¿qué deben cumplir m1 y m2 para que Rm1  Rm2 ?
•Otro ejemplo: Sea otra vez A un conjunto finito
cualquiera, y S=P(A) su conjunto potencia.
Consideremos las relaciones R y Q dadas por:
•aRb  a=b
•aQb  |a| = |b|
 Entonces RQ.
[Recuérdese que en este caso a y b son subconjuntos de
A. |a| es el cardinal de a.]
Relaciones
Nota: en realidad siempre se tiene que la relación de
identidad (“=“) es más fina que cualquier otra relación de
equivalencia.
Consideremos el conjunto (S) de todas las
relaciones de equivalencia posibles sobre el
conjunto S.
 Entonces “” es una relación en (S) !!
¿Qué tipo de relación es?
Ejercicio: conteste y demuéstrelo.
Relaciones: cerradura transitiva
Sea R una relación en S, no necesariamente transitiva.
Definimos su cerradura transitiva como la menor
relación R’ tal que RR’ y R’ es transitiva (en el peor de
los casos, puede ser R’=S2).
En el caso de S finito, lo podemos ver como que
“parchamos” R, agregándole los elementos que estén
fallándole a la transitividad, hasta que ya no falla nada.
Ejemplo:
•S=ciudades del mundo
•aRbexiste un vuelo directo de a hasta b
•aR’bse puede llegar de a hasta b en avión
Relaciones: cerradura transitiva
¿Cómo encontrar la cerradura transitiva (S finito)?
Algoritmo de Warshall (visto en EDA)
•Pensamos en la relación como una
matriz binaria, que dice“puedo ir
de a hasta c usando un solo arco”
o “no puedo”.
R’
a
b
c
a b c
0 1 1
0 1 1
0 1 1
b
a
c
R
a
b
c
a b c
0 1 0
0 0 1
0 1 0
•Queremos ahora una matriz
que exprese “puedo ir de i a j”
(usando 1 o más arcos).
Relaciones: cerradura transitiva
•Definamos A=R
•Aplico |S| veces lo siguiente.
•En el paso k-ésimo, Ak[i,j] me dice acaso hay un camino
entre i y j que pase por nodos de índice k ó menor.
Ak [i, j ]  Ak 1[i, j ]   Ak 1[i, k ]  Ak 1[k , j ]
 “ya había camino, o ahora existe un camino porque
existen caminos de i a k, y de k a j”
Relaciones: cerradura transitiva
Algoritmo de Warshall:
Inicialización:
•A = matriz binaria representando R
Iteración:
•Para k=1,...,N
Para todo i,j
A[i,j] = A[i,j]  (A[i,k]  A[k,j])
R’ = relación representada por A
[Se habla del algoritmo de Floyd-Warshall, porque esto es
una variante del de Floyd para caminos más cortos en grafos.}
Cardinal
Volvamos a las funciones. Si fAB es una función,
escribiremos que f:AB.
Decimos que una función f:AB es inyectiva cuando
preserva las diferencias: si ab, entonces f(a)f(b).
Intuitivamente se ve que, para que esto sea posible,
tiene que haber al menos tantos elementos en B
como en A.
Cardinal
Esa intuición se convierte en definición :
decimos que el conjunto A tiene cardinalidad
menor o igual que B si existe una función
inyectiva f:AB. Escribimos |A||B|
Si se tiene |A||B| y además |B||A| (es decir, existen
funciones inyectivas en ambas direcciones), escribimos
|A|=|B|, y decimos que tienen la misma cardinalidad (o
el “mismo cardinal”).
Nota: una función biyectiva es
inyectiva hacia los dos lados, y se
puede usar para probar igualdad de
cardinal. Pero a veces es más cómodo
usar dos funciones distintas.
Cardinal
Para conjuntos finitos la cardinalidad es simple:
identificamos |A| con la cantidad de elementos
que contiene, y |A||B|  A tiene menos
elementos que B.
Para el vacío, ={ }, se tiene ||=0.
Un “singleton” es un conjunto de cardinal 1. Por
ejemplo: {2}, { {2,3} }, {{}}.
Cardinal
La gracia es que la definición funciona también para
conjuntos infinitos.
Ejercicio: sea A finito y B infinito. Demostrar
que |A|<|B|, es decir, que |A||B|, pero |B||A|.
Ejercicio: Sea AB. Demostrar que |A||B|.
•El conjunto infinito “más chico” es N, los números
naturales.
Cardinal
•Los enteros (Z), los racionales (Q), los números pares
(2Z), tienen todos el mismo cardinal que N.
•Se anota 0 (“aleph 0”). Se dice que son “contables”.
•Los reales (R) no tienen el mismo cardinal
que N. Su cardinal, 1, es llamado “el
cardinal del continuo”, y es el mismo
cardinal de [0,1], R2, R3, etc.
 Hablaremos más sobre esto en
transparencias negras, al llegar a
Georg Cantor.
Fin del repaso
Lenguajes
input
Computador
output
Input & Output:
 Información digital
 Secuencia de símbolos
Computador:
•Máquina con estados internos (finitos!)
•Puede que con memoria
 que también es información digital!
Alfabetos y palabras
Por lo tanto, necesitamos algunas nociones sobre cómo
trabajar formalmente con secuencias de símbolos.
ALFABETO:
•Conjunto finito, no vacío, de símbolos.
•Por lo general lo escribiremos 
Ejemplos:
 = {0,1}
 = {a,b}
 = {a,b,c,...,z,0,...,9}
 = {a,...,z,A,...,Z,” “}  ese “ “ es un espacio en blanco
 = {(,)}  los símbolos son “(“ y “)”
Alfabetos y palabras
•Los símbolos son indivisibles; por lo tanto, no
tendremos alfabetos del tipo { a, b, ab }.
•Ya sabemos lo que es 2= . Más en general,
escribiremos
k
 
 





k veces
•Las palabras de largo k con el alfabeto  serán los
elementos de k.
•En este caso anotaremos las tuplas sin paréntesis
ni comas.
Por ejemplo, si ={0,1}, las palabras de largo 2
serán 00,01,10,11.
Alfabetos y palabras
•Usaremos la letra  (o a veces ) para denotar la
palabra vacía, formada por 0 símbolos.
•Definimos 0= {}
•El conjunto completo de palabras con el alfabeto 
se llama estrella de Kleene y corresponde a

  
*
k
k 0
•En ocasiones se quiere excluir a la palabra vacía; en
ese caso se anota


  
k 1
k
Alfabetos y palabras
•Nótese que * es un conjunto infinito (pero
numerable) de palabras, cada una de las cuales tiene
una cantidad finita de caracteres.
•Dada una palabra w*, usaremos |w| [o a veces
length(w)] para denotar su longitud, es decir, la
cantidad de símbolos que la componen.
•Por definición, ||=0.
NOTA: por lo general se usan letras minúsculas
del comienzo del abecedario para denotar
símbolos, mientras que las letras minúsculas del
final del abecedario suelen denotar palabras.
Alfabetos y palabras
•La concatenación de dos palabras se denota
escribiendo una después de la otra. Por lo tanto, si
u=u1u2...un, v=v1...vm, entonces
w=uv será w = u1u2...un v1...vm
•Dados dos conjuntos de palabras A y B, la
concatenación de los conjuntos será
AB = { w: w=uv, uA, vB }
•Esto permite escribir    *
•Nótese que, por otro lado,   { }  
*

•Además se tiene la recursión  k  k 1
Alfabetos y palabras
•Nótese que la concatenación es una operación
asociativa :
(uv)w = uvw = u(vw)
•Además, tiene un elemento neutro:
u = u = u
•Algo que no verifica es conmutatividad: en general,
no se cumple que
uv = vu
•Un conjunto no vacío dotado de una operación
binaria asociativa se llama semigrupo.
•Si además hay unidad (neutro), se llama monoide.
•Ergo, * con la concatenación es un monoide.
Alfabetos y palabras
•Una operación unaria sobre palabras es la
transposición: si u=u1u2...un, entonces su transposición
es
uR = unun-1...u1
Definamos de nuevo la transposición, pero de manera
recursiva (con recursión sobre la longitud de la
palabra):
•Si |v|=0, vR = v.
•Si |v|=k>0, sean  y uk-1 tales que v=u.
Entonces vR = uR.
Alfabetos y palabras
Sean u,v*. Decimos que
•u es un sufijo de v  x*: v=xu
•u es un prefijo de v  x*: v=ux
•u es una subpalabra de v  x,y*: v=xuy
Si los x (ó y) respectivos son no nulos (o sea,
distintos de ), entonces se dice que u es un sufijo
(o prefijo o subpalabra) propio de v.
Si u es subpalabra de v, se anota a veces u  v
o también u v.
Lenguajes
Un lenguaje L sobre un alfabeto , es cualquier
subconjunto de *.
Ejemplo:
  {a,b}
(alfabeto)
*  {l,a,b,aa,ab,ba,bb,aaa,aab,aba, abb,
baa,bab,bba,bbb,aaaa,… ….} (lenguaje “completo”)
L1 = {a,aa,aab}
L2 = {anbn:n>0} = {ab,aabb,aaabbb,…}
• Ambos son lenguajes (subconjuntos de *).
• L1 es finito, mientras que L2 es infinito. Por lo general nos
interesará el caso infinito.
Lenguajes:operaciones
•Nótese que para cualquier alfabeto , L={} y
L= son siempre lenguajes. OJO: son distintos!!
Ya que los lenguajes son simplemente conjuntos, se
aplican las operaciones de conjuntos (respecto al
conjunto universal *).
•Intersección: L1L2 = { u: uL1  uL2 }
•Unión: L1L2 = { u: uL1  uL2 }
•Complemento: LC = * \ L [a veces se escribe L ]
Lenguajes:operaciones
Además las siguientes operaciones se extienden de
manera natural a lenguajes:
•Transposición: LR = { uR: uL }
•Concatenación: L1L2 = { uv: uL1, vL2 }
•Usando eso, definimos
L0= {}
Lk = L Lk-1
y con eso

*
k
L  L ,
k 0


L  L
k
k 1
Es decir, L* está formado por las concatenaciones
de [cero o más] palabras de L.
Lenguajes: cerraduras
Con frecuencia un lenguaje se define como la
extensión de otro, habitualmente como la cerradura
respecto a algo.
Por ejemplo: dado L, podemos considerar su
cerradura respecto a:
•Concatenación (el menor lenguaje que incluya a L
y sea cerrado bajo concatenación)
Coincide con:
L+
Lenguajes: cerraduras
•Transposición (el menor lenguaje que incluya a
L y sea cerrado bajo transposición)
Coincide con:
LLR
•Subpalabras (el menor lenguaje que incluya a L
y a todas las subpalabras de palabras de L)
•Prefijos (el menor lenguaje que incluya a L y a
todos los prefijos de palabras de L)
Lenguajes
Más ejemplos de lenguajes:
•={0,...,9,k,.,-}, L1={w*: w es un RUT válido}
•={a,b}, L2={w*: w contiene una cantidad par de “b”}
•={(,)}, L3={w*: los paréntesis están bien balanceados}
•={0,1}, L4={w*: w es un nº primo}
•={0,1}, L5={w*: w= 1a01b01c01n, n>2, y an+bn=cn}
•=ASCII, L6={w*: w es un programa en ANSI-C que no
se detiene nunca}
Lenguajes
 Como se puede ver de los ejemplos anteriores,
•Un lenguaje puede representar cosas muy simples (L2),
o muy complicadas (L6).
•Suele ser interesante poder responder acaso un string
pertenece o no a un lenguaje dado (L1, L3, L4, L6).
•En algunos casos, es la existencia o no de strings en el
lenguaje lo que interesa! (L5=  teorema de Fermat)
Veremos en algún momento que no todo lenguaje puede ser
reconocido por un computador; y en algunos casos, hay
cotas mínimas para el tiempo o espacio necesarios.
Lenguajes
Ejercicios:
Encuentre la forma de representar:
•Todos los grafos simples orientados, usando un
alfabeto de a lo más 3 caracteres.
•El conjunto de todas las expresiones booleanas
(i.e., fórmulas del tipo (x1x2)x3, x1x2, etc).
•El conjunto de los números primos, usando un
alfabeto con 1 carácter.
Lenguajes
Ejercicios:
Sean L1, L2 y L3 tres lenguajes sobre el alfabeto .
1) Demuestre que
L1 (L2  L3) = L1L2  L1L3
2) Demuestre que
L1 (L2  L3)  L1L2  L1L3
y que esa inclusión es propia (i.e., existen casos
en que no se tiene “=“)..
Expresiones regulares
Las expresiones regulares (ER) son una forma
compacta (y que posiblemente ya conocen) de definir
lenguajes.
Formalmente, definimos las ER de manera recursiva.
Para el alfabeto , definimos:
•Las ER primitivas son , , y todo .
•Si r1 y r2 son ER, entonces
(r1)
r1*
r1+r2
r1r2
también son ER.
Expresiones regulares
Cada ER r describe un lenguaje L(r); para obtenerlo,
aplicamos los operadores correspondientes a la
expresión, listados aquí según su orden de
precendencia:
1. Estrella de Kleene,
L(r1*) = L(r1)*
2. Concatenación,
L(r1r2) = L(r1)L(r2)
3. Unión,
L(r1+r2) = L(r1)L(r2)
Tal como en el álgebra, los paréntesis se usan para
agrupar e imponer orden de evaluación.
Trivialmente, L((r1)) = L(r1)
Expresiones regulares
Ejemplos:
Strings de largo 1
(0+1)  {0, 1}
(0+1)*  {, 0, 1, 00, 01, 10, 11, …}
(0+1)*010
(0+1)*01(0+1)*
Cualquier string
Cualquier string terminado en 010
Cualquier string que incluya 01
Expresiones regulares
Ejemplos:
((0+1)(0+1))*
Strings de largo par
((0+1)(0+1))*+((0+1)(0+1)(0+1))*
Strings de largo divisible
por dos o por tres
Nota: cuando no haya confusión
posible, es posible usar exponentes:
((0+1)2)*+((0+1)3)*
((0+1)2+(0+1)3)*
Strings de largo > 1.
Algo más sobre expresiones regulares
•Usaremos ER para describir lenguajes de manera
compacta.
•En general, se usan para describir patrones en el
texto (no palabras específicas, sino conjuntos de
palabras que siguen un mismo esquema).
•Aparecen por muchos lados: editores de texto,
compiladores, bases de datos, motores de búsqueda,
catálogos...
•No nos detendremos mayormente en ellas, pero
recomiendo: sepan escribir ER. Sacan de apuros en
muchos contextos.
Algo más sobre expresiones regulares
•Escribir ER no es demasiado difícil; lo importante
es saber cuál es la sintaxis precisa en el programa o
lenguaje en cuestión.
•También es bueno conocer los eventuales
“superpoderes” (extensiones no estándar; por
ejemplo, intersecciones de lenguajes, o variables
dentro de una expresión).
•Algunos ámbitos en que es bueno saber que existen:
comando grep en Unix, módulo re en Python,
java.util.regex, perl, búsquedas en code.google.com...
Algo más sobre expresiones regulares
•La sintaxis suele ser similar a la de Perl, excepto en
grep y otras herramientas Unix, que siguen el
estándar POSIX.
•Los detalles en todo caso pueden ser bastante
enredados.
•Lo más simple es igual en casi todas las sintaxis:
. : comodín (un único carácter, que puede ser cualquiera)
x*: cero o más repeticiones de x (estrella de Kleene)
x+: una o más repeticiones de x
x?: x puede aparecer una vez, o ninguna
Algo más sobre expresiones regulares
xy: concatenación
x|y: x ó y (lo que aquí anotamos x+y)
(xy): agrupa caracteres
[abc] : agrupa caracteres; equivale a (a|b|c), o sea, a+b+c
[a-c]: equivale a [abc]
[a-zA-Z]: cualquier letra
x{n}: n repeticiones de x, es decir, xxx...x, n veces.
•Hay caracteres que indican "comienzo de string" o "fin de
string": en Perl, son ^ y $, respectivamente.
Algo más sobre expresiones regulares
Ejemplo, patentes de autos (incluyendo las patentes más
nuevas):
[A-Z]{2} ([A-Z]{2}|[0-9]{2})[0-9]{2}
También hay abreviaturas (con "\", o con [:algo:] en
posix) para conjuntos de caracteres que se usan con
frecuencia, y para representar caracteres usados en la
sintaxis (como el "[").
Algo más sobre expresiones regulares
NO TODO LENGUAJE puede ser representado mediante
expresiones regulares.
•Algunos sistemas (por ejemplo, Perl) le agregan a sus ER
algunos “trucos” extras (como referenciar variables
dentro del string) que permiten representar más
lenguajes que las ER “silvestres”.
•Los textos y softwares suelen llamar expresiones
regulares (regexp) a esas expresiones extendidas,
aunque técnicamente no lo sean. Aquí usaremos el
término solamente para ER propiamente dichas.
Descargar

EDA