Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    Theory of Automata & Formal Languages (Theory of Computation)

    Uploaded by

    Malay Bhatt
    This document discusses regular languages (RLs) and their closure properties. It shows that: 1) RLs are closed under intersection by constructing a DFA for the intersection of two RLs as the Cartesian product of the states of the DFAs for the individual RLs. 2) RLs are closed under union by using DeMorgan's law to show the union is equivalent to the intersection of the complements, and intersections and complements of RLs are also RLs. 3) Examples are given of DFAs recognizing the intersection and union of specific RLs to demonstrate these closure properties.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Theory of Automata & Formal Languages (Theory of Computation)

    Uploaded by

    Malay Bhatt
    42 views7 pages
    This document discusses regular languages (RLs) and their closure properties. It shows that: 1) RLs are closed under intersection by constructing a DFA for the intersection of two RLs as the Cartesian product of the states of the DFAs for the individual RLs. 2) RLs are closed under union by using DeMorgan's law to show the union is equivalent to the intersection of the complements, and intersections and complements of RLs are also RLs. 3) Examples are given of DFAs recognizing the intersection and union of specific RLs to demonstrate these closure properties.

    Original Title

    Chap3_4

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses regular languages (RLs) and their closure properties. It shows that: 1) RLs are closed under intersection by constructing a DFA for the intersection of two RLs as the Cartesian product of the states of the DFAs for the individual RLs. 2) RLs are closed under union by using DeMorgan's law to show the union is equivalent to the intersection of the complements, and intersections and complements of RLs are also RLs. 3) Examples are given of DFAs recognizing the intersection and union of specific RLs to demonstrate these closure properties.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    42 views7 pages

    Theory of Automata & Formal Languages (Theory of Computation)

    Uploaded by

    Malay Bhatt
    This document discusses regular languages (RLs) and their closure properties. It shows that: 1) RLs are closed under intersection by constructing a DFA for the intersection of two RLs as the Cartesian product of the states of the DFAs for the individual RLs. 2) RLs are closed under union by using DeMorgan's law to show the union is equivalent to the intersection of the complements, and intersections and complements of RLs are also RLs. 3) Examples are given of DFAs recognizing the intersection and union of specific RLs to demonstrate these closure properties.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 7

    1/5/2013

    Theory of Automata & Formal Languages (Theory of Computation)

    Compiled By Prof. M. S. Bhatt

    RLs: Intersection, Union & Complement

    1/5/2013

    RLs are closed Under Intersection


    1 1 1 0 p0 0 p1 q0 0 1 q1 0 q2

    The construct gives:

    0/1 = Q1 x Q2 = {[p0, q0], [p0, q1], [p0, q2], [p1, q0], [p1, q1], [p1, q2]}
    = {0, 1} = {[p1, q2]}

    start state = [p0, q0]


    3

    Some examples:

    ([p0, q2], 0) = [1(p0, 0), 2(q2, 0)] = [p1, q2] ([p1, q2], 1) = [1(p1, 1), 2(q2, 1)] = [p1, q2]

    Final Result:
    1 p0, q0 0 0 p1, q0 1 1 p1, q1 1 p0, q1 1 p0, q2 0 0 p1, q2 1 0

    1/5/2013

    A direct construction of a DFA M such that L( M ) Let: M1 = (Q1, , 1,p0,F1), where Q1 = {p0, p1,} M2 = (Q2, , 2,q0,F2), where Q2 = {q0, q1,} where L(M1) = L1 and L(M2) = L2.

    L1

    L2

    Construct M where: Q = Q1 x Q2 each = {[p0, q0], [p0, q1], [p0, q2],} and M2 F = as with M1 and M2 = F1 x F2 Note that M has a state for

    pair of states in M1

    start state = [p0, q0]


    5

    ([pi, qj], a) = [1(pi, a), 2(qj, a)] and a in

    for all [pi, qj] in Q

    RLs are closed Under Intersection


    q0 b a q2 a b p1 a b p2

    p0

    p3 a

    q1

    1/5/2013

    RLs are closed Under Intersection


    q0 b a q1 a b a q2

    p0

    p3 a

    p1
    qo p0 a b q1 p1 a

    p2

    q2 p3

    Closure Under Intersection Proof 2


    DeMorgans Law: L1L2 = L1 U L2 L1 and L2 are regular So L1 and L2 are regular (Closure under complementation) So L1 U L2 is regular (Closure under union) So L1 U L2 is regular. (Closure under comp.) So L1 L2 is regular.

    1/5/2013

    RLs are closed Under Union


    1 1 1 0 p0 0 p1 q0 0 1 q1 0 q2

    The construct gives:

    0/1 = Q1 x Q2 = {[p0, q0], [p0, q1], [p0, q2], [p1, q0], [p1, q1], [p1, q2]}
    = {0, 1} = {[p1, q2], [p1, q0], [p1, q1], [p0, q2] }

    start state = [p0, q0]


    9

    Some examples:

    ([p0, q2], 0) = [1(p0, 0), 2(q2, 0)] = [p1, q2] ([p1, q2], 1) = [1(p1, 1), 2(q2, 1)] = [p1, q2]

    Final Result:
    1 p0, q0 0 0 p1, q0 1 1 p1, q1 1 p0, q1 1 p0, q2 0 0 p1, q2 1 0

    10

    1/5/2013

    RLs are closed Under Union


    q0 b a q1 a b a q2

    p0

    p3 a

    p1

    p2

    RLs are closed Under Union


    q0 b a q2 a b p1 qo p0 a b q1 p1 a a b p2

    p0

    p3 a

    q1

    q2 p3

    1/5/2013

    Closure Under Union Proof 2 DeMorgans Law: L1 U L2 = L1 L2 L1 and L2 are regular So L1 and L2 are regular (Closure under complementation) So L1 L2 is regular (Closure under intersection) So L1 L2 is regular. (Closure under comp.) So L1 U L2 is regular.

    You might also like