CERRADURAS

              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:

                                                        CERRADURAS

              FECHA DE ENTREGA:

MAYO DE 2015.   

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 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

•          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