Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 34 views

    DFA Construction Ideas

    Uploaded by

    Inderpreet Singh
    differential finite automata, paper on construction of DFA, ideas and paper on how they are created, and their basics

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    DFA Construction Ideas

    Uploaded by

    Inderpreet Singh
    34 views4 pages
    differential finite automata, paper on construction of DFA, ideas and paper on how they are created, and their basics

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    differential finite automata, paper on construction of DFA, ideas and paper on how they are created, and their basics

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    34 views4 pages

    DFA Construction Ideas

    Uploaded by

    Inderpreet Singh
    differential finite automata, paper on construction of DFA, ideas and paper on how they are created, and their basics

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    CSE2001, Fall 2006 1

    Closure Properties of Regular Languages


    Denition: A set S is said to be closed under some operation Op, if, whenever Op is
    applied to the members of S, the result is also a member of S.
    Theorem: The class of regular languages is closed under complement. That is, if L
    is a regular language, the so is L.
    Proof Let L be a regular language over some alphabet . Since L is regular, there
    exists a DFA M = (Q, , , q
    0
    , F) which recognizes L. To prove that L is regular, we
    will construct a DFA M

    that recognizes L.
    The idea: Take M

    to be exactly that same as M, except the set of accepting states


    for M

    is Q F.
    To prove correctness show that w L if and only if M

    accepts w. For this we observe


    that since the set of states, the initial state and the transition function of M and
    M

    are exactly the same, (r


    0
    , r
    1
    , . . . , r
    n
    ) is a computation of M on w if and only if
    (r
    0
    , r
    1
    , . . . , r
    n
    ) is a computation of M

    on w.
    Now, take w L . . .
    Exercise: Complete the details of the above argument.
    Theorem: The class of regular languages is closed under union and intersection. That
    is, if L
    1
    and L
    2
    are regular languages, the so are L
    1
    L
    2
    and L
    1
    L
    2
    .
    Proof Lets start with the union. For simplicity, let us assume that L
    1
    and L
    2
    are languages over the same alphabet . Since L
    1
    is regular, there exists a DFA
    M
    1
    = (Q
    1
    , ,
    1
    , q
    1
    , F
    1
    ) which recognizes L
    1
    . Similarly, there exists a DFA M
    2
    =
    (Q
    2
    , ,
    2
    , q
    2
    , F
    2
    ) which recognizes L
    2
    .
    To prove that L
    1
    L
    2
    is regular, we will construct a DFA M

    which recognizes L
    1
    L
    2
    =
    {w|w L
    1
    or w L
    2
    }.
    The idea: M

    = (Q, , , q
    0
    , F) simulates a parallel execution of M
    1
    and M
    2
    . M

    is
    dened as follows:
    Q = Q
    1
    Q
    2
    ;
    is the same;
    ((q
    1
    , q
    2
    ), a) = ((q
    1
    , a), (q
    2
    , a));
    q
    0
    = (q
    1
    , q
    2
    );
    F = {(r
    1
    , r
    2
    ) | r
    1
    F
    1
    or r
    2
    F
    2
    }
    CSE2001, Fall 2006 2
    To prove correctness we need to show that w L
    1
    L
    2
    if and only if M

    accepts w.
    This, in turn, follows from the fact that (r
    0
    , r
    1
    , . . . , r
    n
    ) is a computation of M
    1
    on w, and
    (t
    0
    , t
    1
    , . . . , t
    n
    ) is a computation of M
    2
    on w, if and only if ((r
    0
    , t
    0
    ), (r
    1
    , t
    1
    ), . . . , (r
    n
    , t
    n
    ))
    is a computation of M

    on w.
    Exercise: Complete the details of the above argument (Hint: use induction).
    Exercise: What would the DFA that accepts L
    1
    L
    2
    look like ?
    Corollary: Every nite language is regular.
    Theorem: The class of regular languages is closed under concatenation and Kleenes
    star operation. That is, if L
    1
    and L
    2
    are regular languages, the so are L
    1
    L
    2
    and L

    1
    .
    The proof based on the idea of concetenation of two DFAs will not y (Why ?). The
    proof of this fact will require some new concepts.
    CSE2001, Fall 2006 3
    Non-deterministic Finite Automata
    A non-deterministic nite automaton (NFA) is a generalization of DFA with the fol-
    lowing two changes:
    In DFA for each pair (q, a) with q Q, q , the transition function gave
    exactly one next state. In NFA, for each pair (q, a) the transition function may
    give 0, 1, or more than one next states.
    0 next states (q, a) is not dened.
    In this case, if the NFA is in state q and receives input symbol a, it will reject
    the rest of the input, regardless of what it is (it dies). This is similar to
    going into a trap state.
    q
    0
    q
    1
    0
    0, 1
    In this NFA, the transition (q
    0
    , 1) is not dened. Thus, every string that
    starts with 1 will kill the NFA immediately, and so will be rejected.
    1 next state (q, a) = r.
    In this case, the NFA in state q on input symbol a will behave just like a DFA
    it will transition to state r.
    Multiple next states (q, a) = {r
    1
    , r
    2
    , ..., r
    n
    }.
    In this case, the NFA in state q on input symbol a splits itself into n copies.
    Copy i goes into the state q
    i
    . All the copies are now run in parallel to each
    other.
    q
    0
    q
    1
    q
    2
    q
    3
    0
    0
    0
    q
    0
    q
    1
    q
    2
    0, 1
    1 1
    CSE2001, Fall 2006 4
    In DFA a transition from state state occures only when a new input symbol is con-
    sumed. In NFA, some transitions (called -transitions) occur without consuming
    any input symbols.

    You might also like