OPERACIONES CON CONJUNTOS

...

La Inclusión cuando cualquier elemento de A que este en B, o cualquier elemento de B que este en A, ó que sean iguales. Por ejemplo si A={2, 4, 5, 7, 8} y B={2, 4}, entonces A⊂B={2, 4}.

La cardinalidad de un conjunto es el número de elementos de ese conjunto. Por ejemplo si A={a, b} entonces |A|=2. La cardinalidad del conjunto vacío es 0 porque no tiene ningún elemento.

Todos los conjuntos aquí tratados se consideran subconjuntos de un conjunto universal U. Los complementos pueden ser formados con respecto a este conjunto universal. Si A es un conjunto, entonces U- A es el conjunto de todos los elementos que no están en A. Conviene denotar tales complementos mediante A, de forma que U- A = A. Obsérvese que ∅=U y U = ∅.[pic 1][pic 2][pic 3][pic 4]

1.3. ALFABETOS.

Un alfabeto es un conjunto no vacío y finito de símbolos. En el caso del alfabeto inglés, la colección finita es el conjunto de las letras del alfabeto junto con los símbolos que se usan para construir palabras en inglés (tales como el guión, el apóstrofe y otros por el estilo).

Cada símbolo de un alfabeto es una cadena sobre dicho alfabeto. La cadena vacía, la cual se denota por el símbolo ε, es una palabra sobre cualquier alfabeto.

1.4. PROPIEDADES DE LAS CADENAS O “STRINGS”.

Una cadena (ó palabra) es una secuencia finita de símbolos. Por ejemplo: a, b y c son símbolos y abcb es una cadena.

1.4.1. Cadena Vacía.

La cadena vacía, denotada por ε es la cadena que consiste en cero símbolos. Por tanto, tiene longitud |ε|=0.

1.4.2. Longitud.

Si w es una cadena sobre cualquier alfabeto, su longitud se denota como |w |. La longitud de w es el número de símbolos que tiene la cadena. Por ejemplo: abcb tiene longitud |w | =4.

1.4.3. Concatenación.

La concatenación de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas. Por ejemplo: si w= “banana” y z= “rama”, la concatenación de w con z es la cadena “bananarama”. La concatenación de las cadenas w y z se denota como wz ó w.z. La cadena vacía es la identidad para el operador de concatenación. Es decir, εw= wε=w para cada cadena w.

1.4.4. Potencia de Cadenas.

La noción de potencia de una cadena sobre un alfabeto es dada por la notación wk que denota la concatenación de k copias de la cadena w.

Por tanto, si w=122 sobre el alfabeto Σ={1, 2}, se tiene

w0 = ε

w1 = 122

w2 = 122122

w3 = 122122122

1.4.5. Igualdad de Cadenas.

Si w y z son cadenas, se dice que w es igual a z, si tienen la misma longitud y los mismos símbolos en la misma posición. Se denota mediante w =z.

1.4.6. Prefijo.

Los prefijos de una cadena están formados por los primeros símbolos de ésta. Por ejemplo, la cadena 121 sus prefijos son: ε, 1, 12 y 121, con lo que toda palabra puede considerarse prefijo de sí misma. Un prefijo de una cadena que no sea la misma cadena es un prefijo propio.

4321

1.4.7. Sufijo.

Los sufijos de una cadena están formados por los últimos símbolos de está. Por ejemplo, la cadena abc sus sufijos son: ε, c, bc y abc. Un sufijo de una cadena que no sea la misma cadena es un sufijo propio.

1.4.8. Subcadena.

Una cadena w es una subcadena o subpalabra de otra cadena z si existen las cadena x e y para las cuales z= xwy.

1.4.9. Transpuesta.

La inversa o transpuesta de una cadena w es la imagen refleja de w. Por ejemplo, si w = ”able” entonces su inversa es “elba”. Para denotar la inversa de w se usa wI.

wI

1.5. REPRESENTACIÓN FINITA DEL LENGUAJE.

Un alfabeto es un conjunto finito de símbolos.

Un lenguaje (formal) es un conjunto de cadenas de símbolos tomados de algún alfabeto. El conjunto vacío, ∅ y el conjunto formado por la cadena vacía {ε} son lenguajes. Nótese que son diferentes: el último tiene un elemento, mientras que el primero no. El conjunto de Palíndromos (cadenas que se leen igual de izquierda a derecha y viceversa) sobre el alfabeto {0,1} es un lenguaje infinito. Algunos elementos de este lenguaje son ε, 0, 1, 00, 11, 010 y 1101011.

Otro lenguaje es el conjunto de cadenas sobre un alfabeto fijo Σ. Denotamos a este lenguaje como Σ* llamado como la cerradura de Kleene o cerradura de estrella de un lenguaje. Las cadenas de la cerradura de Kleene se forman al realizar cero o más concatenaciones de las cadenas del alfabeto, mientras que la cerradura positiva se forma al realizar una o más concatenaciones. Por ejemplo si Σ={a}, entonces tenemos que Σ0= {ε}, Σ1={a}, Σ2= {aa} y así sucesivamente. Por tanto Σ*=