Introducci n a la Teor a de la Computaci n

Teoría de la Computación
Clase Teórica Nº 1
Introducción a la Teoría de la Computación.

Objetivos
Al final de la clase los estudiantes serán capaces de:


Utilizar conceptos y conocimientos matemáticos en la teoría de la computación.



Aplicar las diferentes técnicas de formulación de pruebas.



Comprender la importancia de los lenguajes y su construcción.

Introducción
En esta primeraclase repasaremos brevemente algunas nociones y notaciones que serán necesarias para
comprender adecuadamente el resto de temas de la asignatura. Debe, sin embargo, quedar claro que este repaso
queda fuera del área de autómatas y lenguajes formales. Un objetivo importante de este primer contenido es
uniformizar la notación, que varía bastante de libro a libro.

Desarrollo

Conjuntos.
El fundamento másimportante para el estudio de los lenguajes y autómatas es la Teoría de Conjuntos. En efecto,
siempre que hablemos de “formalizar” una noción, estaremos diciendo en realidad “expresar en términos de la
Teoría de Conjuntos”. Es por esto que en esta clase presentamos los conceptos más básicos de dicha Teoría de
Conjuntos.
La idea de un conjunto como una colección de individuos u objetos no es, paraun verdadero matemático,
suficientemente precisa, y se parece a la noción de clase; sin embargo, para nuestros propósitos es suficiente.
Un conjunto que vamos a utilizar con frecuencia es el de los números naturales, {1, 2, 3,...}, denotado por N.
Los conjuntos pueden expresarse de dos maneras básicamente:
A. En extensión, lo cual quiere decir que citamos explícitamente cada uno de sus elementos,como en el
conjunto {1, 3, 5} que contiene exactamente los números 1, 3 y 5.
B. En intención, dando una descripción precisa de los elementos que forman parte del conjunto, en vez de
citarlos explícitamente. Por ejemplo, el conjunto del punto anterior puede ser visto como {i ∈ N/ impar
(i), i < 6}, donde se supone que los números impares cumplen la condición impar (i).____________________________________________________________________________________________________________________________
Teoría de la Computación. Ciclo I/2015
1

Representamos a los conjuntos con letras mayúsculas, como en A = {2, 4}. Los conjuntos pueden contener
conjuntos como elementos, como en B = {{a}, {b, c}}. El conjunto sin elementos (vacío) se representa por ∅ o
bien por { }.
La notación a ∈ B significa que aes elemento o está contenido en el conjunto B; por ejemplo, {2, 3} ∈ {1, {2, 3},
4}. Para indicar que a no está en B se escribe a  B.

El tamaño de un conjunto es el número de elementos que contiene, y se representa como |A| para un conjunto A.
Por ejemplo, el tamaño de {a, b, c} es 3, y el tamaño de ∅ es cero. Por ejemplo, el tamaño de {{a}, {b, c}} es 2 y
no 3, pues tiene 2 elementos, siendoel primero {a} y el segundo {b, c}.
La definición de “tamaño” parece muy clara, pero hay conjuntos que no tienen un número determinado de
elementos; estos se llaman “infinitos” y serán discutidos más adelante.
Dos conjuntos A y B son iguales, A = B, si y sólo si tienen los mismos elementos, esto es, x ∈ A ssi x ∈ B.1 Por
ejemplo, {1, {2, 3}} = {{3, 2}, 1}; vemos que en los conjuntos el orden de loselementos es irrelevante.
Se supone que en los conjuntos no hay repeticiones de elementos, y que cada elemento del conjunto es distinto de
todos los otros elementos. Sin embargo, si decimos, por ejemplo, i ∈ A, j ∈ A, no estamos suponiendo que i sea
distinto de j, pues tanto i como j son elementos cualesquiera de A. Si necesitamos que sean distintos, hay que
indicarlo explícitamente, como en laexpresión i, j ∈ A, i ≠ j.
La notación A ⊆ B significa que el conjunto A está “contenido” en el conjunto B, o más técnicamente, que A es
subconjunto de B. Por ejemplo, el conjunto {a, c} es subconjunto de {a, b, c}, indicado como {a, c} ⊆ {a, b, c}.
En otras palabras, A ⊆ B cuando siempre que x ∈ A, tenemos también x ∈ B.
Obsérvese que de acuerdo con esta definición, A ⊆ A para cualquier conjunto...