Operaciones con Conjuntos

Las operaciones habituales que se definen sobre los conjuntos son:

El conjunto Æ llamado conjunto vacío o nulo, no tiene elementos. El conjunto vacío es un subconjunto de todos los conjuntos.

La unión de conjuntos A y B se denota por A È B y es un conjunto formado por los elementos que aparecen en A, en B o en ambos.

Por lo tanto A È B ={x|xΠA ó x ΠB}.

Por ejemplo, si A={1, 2, 3} y B= {a, b}, entonces A È B={1, 2, 3, a, b}.

La intersección de A y B es el conjunto de todos los elementos que aparecen simultáneamente en A y también en B.

Por lo tanto A Ç B ={x|xΠA y x ΠB}.

Por ejemplo, si A={1, 4, 5, 7} y B= {2, 4, 7, 8}, entonces A Ç B={4, 7}.

El complemento relativo si A y B son dos conjuntos cualesquiera, el complemento de B con respecto a A es el conjunto: A-B={x|xΠA y xÏ B}.

Por lo tanto, A-B esta compuesto por todos los elementos de A que no están también en B. Por ejemplo, si A={0, 2, 4, 6, 8, 10} y B={0,1, 2, 3, 4}, entonces A-B={6, 8, 10}, mientras que B-A={1, 3}.

2A , el conjunto potencia de A, es el conjunto formado por todos los subconjuntos de A. Por ejemplo, sea A={a, b, c} . Entonces 2A ={Æ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Dados dos conjuntos A y B, su producto cartesiano, AxB, es el conjunto de todos los pares ordenados de los que el primer elemento proviene de A y el segundo de B. Así que, AxB ={(a, b)|aΠA y bΠB}. Por ejemplo, sí A={1,2,3} y B={5,6} entonces: AxB ={(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)}.

Si A y B son conjuntos y todos los elementos de A son también elementos de B, se escribe A Í B y se dice que A es un subconjunto de B. Por ejemplo A={1,2,3} y B={0,1,2,3,4,5} , se tiene A Í B. Por otro lado, B no es un subconjunto de A, porque los elementos 0, 4 y 5 de B no lo son de A.

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 = Æ .

Cerradura

Una clase de lenguajes L es un álgebra si es cerrada por unión y complemento y si contiene al conjunto vacío. Es decir, si se cumplen las propiedades 

En una clase de lenguaje, además de caracterizar la solubilidad de los problemas de la palabra y de derivación, mencionados en la Introducción del curso, también es importante decidir si acaso una clase dada de lenguajes en un álgebra. Por ejemplo, la clase de lenguajes regulares sobre un alfabeto finito forma un álgebra de conjuntos. La clase de lenguajes recursivamente enumerables, es decir, aquellos que son generados por gramáticas irrestrictas, contiene al conjunto vacío, y la unión y la intersección de cualesquiera dos lenguajes en la clase están en la clase, sin embargo no ocurre lo mismo para la operación de complementación. En general, si Ø es un operador de aridad k, que transforma k lenguajes dados en algún otro lenguaje, un problema importante para una clase L de lenguajes es decidir cuándo esa clase es cerrada bajo el operador, es decir, cuándo rige la implicación: 

Expresiones Regulares

Los lenguajes aceptados por un autómata finito se describen con facilidad mediante expresiones simples llamadas expresiones regulares.

Sea S un alfabeto. La expresión regular sobre S y los conjuntos que denotan se definen de manera recursiva como sigue:

1.       Æ es una expresión regular y denota al conjunto vacío.

1.       e es una expresión regular y denota al conjunto {e }.

1.       Para cada a Î S , a es una expresión regular y denota al conjunto {a}.

1.       Si r y s son expresiones regulares que denotan a los lenguajes R y S.; respectivamente, entonces tenemos lo siguiente:

r+s es una expresión regular que denota a los conjuntos R È S.

(r) es una expresión regular que denota al conjunto R.

rs es una expresión regular que denota a los conjuntos RS.

r* es una expresión regular que denota al conjunto R*.

r+ es una expresión regular que denota al conjunto R+.

ri es una expresión regular que denota al conjunto Ri.

Existen muchas equivalencias con respecto a expresiones regulares basadas en las correspondientes igualdades de lenguajes. Por ejemplo sean r, s y t expresiones regulares sobre el mismo alfabeto S . 
Entonces:

1.       r + s = s + r

2.       (rs)t = r(st)

3.       (r + s)t = rt + st

4.       (r*)* = r*

5.       r(s + t) = rs + rt

Un problema común en la programación de computadoras es el de tener la seguridad de que los datos de entrada de un programa son correctos. La programación cuidadosa pretende construir un programa que analice la información introducida por el usuario y, de alguna forma, prevenir que se aplique información incorrecta al programa. Si pudiéramos construir un autómata finito que aceptara solamente las cadenas que representan información correcta, entonces tendríamos un modelo para dicha rutina de entrada. Puesto que los autómatas finitos se corresponden con las expresiones regulares, el problema se reduce a especificar la información correcta por medio de expresiones regulares.

Fractal

Un fractal es un objeto geométrico cuya estructura básica, fragmentada o irregular, se repite a diferentes escalas.  La propiedad matemática clave de un objeto genuinamente fractal es que su dimensión métrica fractal es un número no entero.

A un objeto geométrico fractal se le atribuyen las siguientes características:

·         Es demasiado irregular para ser descrito en términos geométricos tradicionales.

·         Es autosimilar, su forma es hecha de copias más pequeñas de la misma figura.

Las copias son similares al todo: misma forma pero diferente tamaño. Ejemplos de autosimilaridad:

Fractales naturales son objetos naturales que se pueden representar con muy buena aproximación mediante fractales matemáticos con autosimilaridad estadística. Los fractales encontrados en la naturaleza se diferencian de los fractales matemáticos en que los naturales son aproximados o estadísticos y su autosimilaridad se extiende sólo a un rango de escalas (por ejemplo, a escala cercana a la atómica su estructura difiere de la estructura macroscópica).

 Conjunto de Mandelbrot es un fractal autosimilar, generado por el conjunto de puntos estables de órbita acotada bajo cierta transformación iterativa no lineal.

 Paisajes fractales, este tipo de fractales generados computacionalmente pueden producir paisajes realistas convincentes.

 Fractales de pinturas, se utilizan para realizar el proceso de decalcomania.

Su dimensión de Hausdorff-Besicovitch es estrictamente mayor que su dimensión topológica.

 Se define mediante un simple algoritmo recursivo.

Notación de Expresiones Regulares

Expresión Regular: Lenguaje para procesar textos mediante reconocimiento de patrones. Su sintáxis es similar a cadenas con metacaracteres y metasecuencias para representar patrones. Ejemplo: 'b+' significa una o más repeticiones de la letra 'b'

Expresiones Regulares

Símbolo	Descripción
^x	Iniciar con x
x$	Terminar en x
(x)	Agrupa y graba x en RegExp.$1..9
(?:x)	Agrupa pero no registra en RegExp.$1..9
x.	x seguido de una letra cualquiera
x|y	x ó y
[xy]	x ó y (conjunto de letras)
[x-z]	x ó y ó z (rango)
[^xy]	Ni x ni y (complemento)
x*	x cero o más veces
x+	x una o más veces
x?	x cero o una vez
x{2}	x dos veces
x{1,4}	x de una a cuatro veces
x{2,}	x al menos dos veces

Evaluación de un Autómata 

M1: 1000111

ɖ(q0,1)={q0,q1}= ɖ(q0,10)={q0,q3)=d(d(q0,100),0)={q0,q3}= ɖ(q0,100)={q0,q3}= ɖ(q3,1001)= Ǿ= ɖ(q1,10001)=q2= ɖ(q3,100011)= Ǿ =ɖ(q3,1000111)= Ǿ= ɖ(q2,1000111)=q2

cadena aceptada

M2=1111000

ɖ(q0,1)={q0,q1}= ɖ(q1,11)=q2= ɖ(q2,111)=q2 = ɖ(q2,11110)=q2= ɖ(q2,111100)=q2= ɖ(q2,1111000)=q2

cadena aceptada