CONJUNTOS Y SUS OPERACIONES

              CENTRO UNIVERSITARIO UAEM 

              ATLACOMULCO

            LICENCIATURA EN INGENIERÍA EN COMPUTACIÓN

              NOMBRE DEL DOCENTE:

         INGENIERO. HÉCTOR CABALLERO HERNÁNDEZ

              NOMBRE MATERIA:

AUTÓMATAS Y LENGUAJES FORMALES

              NOMBRE DE LA ALUMNA:

HEIVILINA PÉREZ ARIAS

              GRUPO:

ICO-19

              TURNO:

MATÚTINO

               TRABAJO A ENTREGAR:

                            CONJUNTOS Y SUS OPERACIONES

              FECHA DE ENTREGA:

MAYO DE 2015.   

CONJUNTO

Es la reunión en un todo de objetos bien definidos y diferenciables entre sí, que se llaman elementos del mismo.

Un conjunto se suele denotar encerrando entre llaves a sus elementos, si se define por extensión, o su propiedad característica, si se define por comprensión. 

OPERACIONES CON CONJUNTOS:

Unión de conjuntos:

Al realizar esta operación estamos conformando un nuevo conjunto, que se llama conjunto solución,  que contiene todos los elementos o miembros de los conjuntos que se estén uniendo, sin que ninguno de sus miembros se repita en el conjunto solución.

La unión de dos conjuntos A y B la denotaremos por A È B y es el conjunto formado por los elementos que pertenecen al menos a uno de ellos ó a los dos. Lo que se denota por:

A È B = {x/x Î A ó x Î B}

 Ejemplo: Sean los conjuntos A= {1, 3, 5, 7, 9} y B= {10, 11, 12}

A È B = {1, 3, 5, 7, 9, 10, 11, 12}

Intersección de conjuntos:

Esta operación entre conjuntos conforma un nuevo conjunto que contenga los elementos o miembros comunes a los conjuntos que hagan parte de esta operación.

Sean A= {1, 2, 3, 4, 5, 6, 8, 9} y B= {2, 4, 8, 12}

Los elementos comunes a los dos conjuntos son: {2, 4, 8}. A este conjunto se le llama intersección de A y B; y se denota por A Ç B, algebraicamente se escribe así:

A Ç B = {x/x Î A y x Î B}

Y se lee el conjunto de elementos x que están en A y están en B.

Ejemplo:

Sean Q= {a, n, p, y, q, s, r, o, b, k} y P= {l, u, a, o, s, r, b, v, y, z}

Q Ç P= {a, b, o, r, s, y}

Diferencia de conjuntos:

Sean A y B dos conjuntos. La diferencia de A y B se denota por A-B y es el conjunto de los elementos de A que no están en B y se representa por comprensión como:

A - B= {x/x Î A; X Ï B}

Ejemplo:

Sea A= {a, b, c, d} y

B= {a, b, c, g, h, i}

A - B= {d}

En el ejemplo anterior se observa que solo interesan los elementos del conjunto A que no estén en B. Si la operación fuera B - A el resultado es

B – A = {g, h, i}

E indica los elementos que están en B y no en A.

Complemento de un conjunto:

Se buscan todos los elementos que le hagan falta a un conjunto para convertirse o ser el conjunto universal o referencial. El complemento de un conjunto respecto al universo U es el conjunto de elementos de U que no pertenecen a A y se denota como A' y que se representa por comprensión como:

A'= {x Î U/x y x Ï A}

 Ejemplo:

Sea U = {1, 2, 3, 4, 5, 6, 7, 8, 9}

A= {1, 3, 5, 7, 9} donde A Ì U

El complemento de A estará dado por:

A'= {2, 4, 6, 8}

CERRADURAS

*Los conjuntos regulares son cerrados bajo las operaciones de:

Ø  Unión

Ø  Intersección

Ø  Complemento

Ø  Concatenación

Ø  Estrella de Kleene

 Nota: en las demostraciones siguientes se supondrá que los autómatas son completos, i.e., que la función δ no es parcial.

Demostración de cerradura bajo unión:

Sean D1 = (Q1 , Σ, δ1 , s1 , F1) y D2 = (Q2 , Σ, δ2 , s2 , F2) dos DFA.

Construiremos un D ∈ DFA tal que:

                                      L (D) = L(D1) ∪ L(D2).

 Definimos D = (Q, Σ, δ, s, F) donde:

Q = Q1 × Q2

 s = (s1 , s2)

                                      F = (Q1 × F2) ∪ (F1 × Q2)

δ((q1 , q2), a) = (δ1(q1 , a), δ(q2 , a))

 Se puede demostrar por inducción en α que:

α ∈ L (D) si α ∈ L (D1) o bien α ∈ L(D2).

Demostración de cerradura bajo unión y complemento:

Intersección:

 Se construye un autómata como en el caso de ∪, salvo que:

                                                           F = F1 × F2.

 Complemento:

 Sea A = (Q, Σ, δ, s, F) un DFA. Sea A¯ = (Q, Σ, δ, s, Q − F).

 Claramente:

 L (A¯) = Σ ∗ − L(A).

Demostración de cerradura estrella de Kleene:

L:a clausura (o asterisco, o clausura de Kleene)1 de un lenguaje L se designa mediante L∗ y representa

El conjunto de cadenas que se pueden formar tomando cualquier número de cadenas de L, posiblemente

con repeticiones (es decir, la misma cadena se puede seleccionar más de una vez) y concatenando todas

ellas.

Ejemplo:

L = {0,1}, entonces L∗ es igual a todas las cadenas de 0s y 1s. Si L = {0,11},

entonces L∗ constará de aquellas cadenas de 0s y 1s tales que los 1s aparezcan por parejas, como por ejemplo 011, 11110 y ε , pero no 01011 ni 101. Más formalmente, L∗ es la unión infinita ∪i≥0 Li, donde

L0 = {ε }, L1 = L y Li, para i > 1 es LL· · ·L (la concatenación de i copias de L).

Demostración de cerradura bajo concatenación y estrella de Kleene:

Sean A = (QA, Σ, δA, sA, FA) y B = (QB, Σ, δB, sB, FB) dos DFA. El autómata C = (QC, Σ, ∆C, SC, FC) se construye de la siguiente forma

                                      QC = QA ∪ QB

                                       SC = {sA}

FC = FB

                            ∆ (q, a) = {δA(q, a)} si q ∈ QA

∆ (q, a) = {δB(q, a)} si q ∈ QB

∆ (q, ) = {sB} si q ∈ FA

 C es un NFA-tal que L(C) = L(A) L(B). Para construir A 0 tal que:

 L(A 0) = L(A) ∗ , se añaden transiciones-de los estados en FA a sA.

Ejemplo:

•         L = {0, 11}

–        L⁰ = {l}

–        L¹ = {0, 11}

–        L² = {00, 011, 110, 1111}

–        L³ = {000, 0011, 0110, 01111, 1100, 11011, 11110, 111111}

–        L⁴ = {0000, 00011, 00110, 001111, 01100, 011011, 011110, 0111111, 11000, 110011, 110110, 1101111, 111100, 1111011, 1111110, 11111111}

L^* son todas las que se pueden formar concatenando cualquier número de veces (excepto¥) palabras de L.

NOTACION DE EXPRESIONES REGULARES

Todos los tipos de álgebras se inician con las expresiones elementales, que normalmente son constantes y/o variables. Las álgebras nos permiten construir más expresiones aplicando un cierto conjunto de operadores a las expresiones elementales y a las expresiones previamente construidas. Normalmente, también se necesitan algunos métodos que permitan agrupar operadores con sus operandos, tales como los paréntesis. El álgebra de las expresiones regulares sigue también este patrón, utilizando constantes y variables que representan lenguajes y operadores para (la unión, el punto y el asterisco). Se puede describir las expresiones regulares recursivamente del siguiente modo. En esta definición, no sólo describimos lo que son las expresiones regulares válidas, sino que para cada expresión regular

E, describimos el lenguaje que representa, al que denominaremos L (E).

Base: El caso básico consta de tres partes:

1. Las constantes ε y /0 son expresiones regulares, que representan a los lenguajes {ε} y /0, respectivamente.

                            L (ε) = {ε} y L( /0) = / 0.

2. Si a es cualquier símbolo, entonces a es una expresión regular. Esta expresión representa el lenguaje {a}.

Es decir, L(a)={a}.Observe que utilizamos la fuente en negrita para indicar la expresión correspondiente a un símbolo. La correspondencia, por ejemplo, que a hace referencia a a, es obvia.

3. Una variable, normalmente escrita en mayúsculas e itálicas, como L, representa cualquier lenguaje.

Paso inductivo. Existen cuatro partes en el paso de inducción, una para cada uno de los tres operadores y otra para la introducción de paréntesis.

1. Si E y F son expresiones regulares, entonces E +F es una expresión regular que representa la unión de:

L(E) y L(F). Es decir, L(E +F) = L(E) ∪ L(F).

2. Si E y F son expresiones regulares, entonces EF es una expresión regular que representa la concatenación de:

 L(E) y L(F). Es decir, L(EF) = L(E)L(F).

El punto puede utilizarse opcionalmente para explicitar el operador de concatenación, bien como una operación sobre lenguajes o como el operador en una expresión regular.

Ejemplo:

 0.1 es una expresión regular que significa lo mismo que 01 y que representa el lenguaje {01}. Sin embargo, para evitar el uso del punto en la concatenación de expresiones regulares.2

3. Si E es una expresión regular, entonces E∗ es una expresión regular, que representa la clausura de L(E).

L(E∗) =L(E)

.

4. Si E es una expresión regular, entonces (E), una E encerrada entre paréntesis, es también una expresión regular, que representa el mismo lenguaje que E. Formalmente; L(E)= L(E).

Ejemplo:

Escribamos una expresión regular para el conjunto de cadenas que constan de 0s y 1s alternos. Primero, desarrollamos una expresión regular para el lenguaje formado por una sola cadena 01. Podemos luego emplear el operador asterisco para obtener una expresión para todas las cadenas de la forma 0101· · ·01.

La regla básica de las expresiones regulares nos dice que 0 y 1 son expresiones que representan los lenguajes

{0} y {1}, respectivamente. Si concatenamos las dos expresiones, obtenemos una expresión regular para el lenguaje {01}; esta expresión es 01. Como regla general, si queremos una expresión regular para el lenguaje formado por una sola cadena w, utilizaremos la propia cadena w como expresión regular. Observe que en la expresión regular, los símbolos de w normalmente se escribirán en negrita, pero este cambio de tipo de fuente es sólo una ayuda para diferenciar las expresiones de las cadenas y no debe considerarse significativo.

•         Tomando en cuenta que la unión y la concatenación son asociativas, además conviniendo en que la precedencia u orden de ejecución de las operaciones está dada por:

–        Paréntesis

–        Cerradura de Kleene

–        Concatenación

–        Unión

         Las expresiones se pueden simplificar aún más reduciendo el número de paréntesis.

–        {a, b}^*{bb}{a, b}^* = (a + b)^*bb(a + b)^*

–        {a}{a, b}^*{b}{a, b}^*{a} = a(a + b)^*b(a + b)^*a

•         Notación

–        u⁺ = uu^*

–        u² = uu,   u³ = u²u,  ...

Ejemplo:

El conjunto {bawab | w Î {a, b}^*} es regular sobre {a, b}
Demostración:
Conjunto                            Expresión               Justificación
1.     {a}                                   a              Base
2.     {b}                                   b              Base
3.     {a}{b}={ab}                     ab            Concatenación de 1 y 2
4.     {a} È {b}={a,b}       a+b           Unión de 1 y 2
5.     {b}{a}={ba}                     ba            Concatenación de 2 y 1
6.     {a,b}^*                               (a+b)^*       Cerradura Kleene de 4
7.     {ba}{a,b}^*                        ba(a+b)^*    Concatenación de 5 y 6
8.     {ba}{a,b}^*{ab}                 ba(a+b)^*ab Concatenación de 7 y 3