foco??

1.1.- Conjuntos finitos e infinitos
 
Un conjunto es una colección de elementos llamados elementos del conjunto.
Si A es un conjunto y “a” es un elemento de A, se usa la notación aA (se lee “a” es un elemento de “A”). Se usa la notación bA cuando es necesario indicar que b no es elemento de A.
Si sabemos que A contiene exactamente los elementos a1, a2, …, an, lo indicamos escribiendo A ={a1, a2, …, an}. Por ejemplo, el conjunto de los números naturales menores  que 6 puede ser escrito A = {0, 1, 2, 3, 4, 5}. Esta notación puede ser extendida a los conjuntos para los cuales no es posible listar todos sus elementos, tales como N = {0, 1, 2, …} o N+ = {1, 2, 3, …}. Un conjunto solo se caracteriza por sus elementos y no por el orden en el cual se listan. Por eso {1,2,3} y {2,1,3}denotan el mismo conjunto.
Los conjuntos A y B son iguales si contienen exactamente los mismos elementos. Por tanto, si A={1,2,3} y B={2,1,3}, se puede escribir A=B.
Fíjese que {a} y a no son lo mismo. Tenemos que aA pero a≠{a}. También el conjunto {{a,b}} tiene un único elemento que es el conjunto {a,b}. Por otro lado, {a,b} tiene dos elementos que son a y b, por consiguiente {{a,b}}≠{a,b}.
Si Ay B son conjuntos y todos los elementos de A son también elementos de  B, se dice que A es un subconjunto de B y se escribe como AB. Por ejemplo si A={1,2,3} y B={0,1,2,3,4,5}, se tiene AB. Por otro lado, B no es subconjunto de A ya que contiene los elementos 0,4,5 y estos no están contenidos en A.
Para completar las definiciones, es conveniente considerar un conjunto especial , llamado vacíoo nulo, el cual no contiene elementos. El conjunto vacío es subconjunto de todos los conjuntos; por lo cual se puede decir que A, para todo conjunto A.
 
M = { x / x es un río de la tierra } Conjunto finito
N = { 0, 1, 2, 3, 4, 5, 6, 7, 8, ... } Conjunto infinito
P = { x / x es un país de la tierra } Conjunto finito
V = { 3, 6, 9, 12, 15, 18, 21, 24, 27, ... } Conjunto infinito
 Alfabetos.-
Es un conjunto y no vacío de símbolos. Por ejemplo el alfabeto en ingles esta conformado por 26 símbolos. En otro contexto se puede considerar como alfabeto a la colección de todas las palabras inglesas como correctas o la colección de todos los símbolos legales en PASCAL como pueden ser identificadores, palabras reservadas, caracteres especiales. Si ∑ es un alfabeto,   ∑ denota que  esun símbolo de ∑. Por tanto si:
 
∑ = {0,1,2,3,4,5,6,7,8,9}
 
…podemos decir que 0  ∑
 
Obsérvese que, puesto que un alfabeto es simplemente un conjunto finito no vacio, dados ∑1 y ∑2 alfabetos, se tiene  que ∑1 ∩ ∑2 también lo es. Es mas, si ∑1 ∩ ∑2, ∑1 - ∑2 y ∑2 ∩ ∑1 son conjuntos no vacíos, también son alfabetos. Una secuencia finita de símbolos de un determinado alfabeto se conoce comopalabra o cadena. Si el alfabeto es el alfabeto ingles, algunas palabras pueden ser PROGRAM, DIGIT, MOON, etc. De esta manera al conjunto de palabras se le denomina lenguaje.

Propiedades de cadenas.-
a) Longitud.
Si w es una cadena sobre cualquier alfabeto, su longitud se denota mediante el símbolo |w|. La longitud de w es el número de símbolos que tiene la cadena. Así que, si w = 121 sobre elalfabeto ∑ = {1,2}, entonces |w| = 3. La cadena vacia , no tiene símbolos con lo que || = 0
 
b) Concatenación.
Si w y z son cadenas, la concatenación de w con z es la cadena que se obtiene al añadir a la cadena w la palabra z. Por ejemplo si w = “banana” y z = “rama”, la concatenación de w con z es la cadena “bananarama”. La concatenación de las palabras w y z se denota como wz o wz.Obsérvese que se tiene que:
 
|wz| = |w| + |z|
 
La concatenación de la palabra vacia  con cualquier otra palabra w no modifica a w. Por esta razón,  se comporta como la identidad con respecto a la operación de concatenación.
 
Lenguajes.-
Un lenguaje es un conjunto de palabras. Por tanto el conjunto {1,12,123,1234,12345,123456} es un lenguaje sobre el alfabeto compuesto por digitos. De...