لخّصلي

Deterministic Finite Automata
Finite Automaton (FA)
◼ Informally, it is a state diagram that
comprehensively captures all possible states and
transitions that a machine can take while
responding to a stream or sequence of input
symbols.
◼ Recognizer for “Regular Languages”.
◼ Deterministic Finite Automata (DFA)
◼ The machine can exist in only one state at any given time.
◼ Non-deterministic Finite Automata (NFA)
◼ The machine can exist in multiple states at the same time.
7
Deterministic Finite Automata
◼ A Deterministic Finite Automaton (DFA)
consists of:
◼ Q = A finite set of states
◼ ∑ = A finite set of input symbols (alphabet)
◼ q0 = A start state
◼ F = A set of accepting states
◼ δ = A transition function, which is a mapping
between Q x ∑ → Q
◼ A DFA is defined by the 5-tuple:
◼
8
What does a DFA do on reading an
input string?
◼ Input: a word w in ∑*
◼ Question: Is w accepted by the DFA?
◼ Steps:
◼ Start at the start state, q0
◼ For every input symbol in the sequence w do
◼ Compute the next state from the current state, given
the current input symbol in w and the transition
function
◼ If after all symbols in w are consumed, the
current state is one of the accepting states (F)
then w is accepted;
◼ Otherwise, w is rejected.
9
Regular Languages
◼ Let L(A) be a language recognized by a DFA
A.
◼ Then L(A) is called a “Regular Language”.
◼ Locate regular languages in the Chomsky
Hierarchy
10
The Chomsky Hierarchy
11
Regular
(DFA)
Contextfree
(PDA)
Contextsensitive
(LBA)
Recursively-
enumerable
(TM)
• A containment hierarchy of classes of formal languages
Example #1
◼ Build a DFA for the following language:
◼ L = {w | w is a binary string that contains 01 as a
substring}
◼ Steps for building a DFA to recognize L:
◼ ∑ = {0, 1}
◼ Decide on the states: Q
◼ Designate start state and final state(s)
◼ δ: Decide on the transitions:
◼ Final states are same as “accepting states”.
◼ Other states are same as “non-accepting states”.
12
DFA for strings containing 01
13
q0
start
q1
0
Regular expression: (0+1)01(0+1)
1 0 0,1
1
q2
Accepting
state
• What if the language allows
empty strings?
• What makes this DFA deterministic? • Q = {q0
, q1
, q2
}
• ∑ = {0, 1}
• start state = q0
• F = {q2
}
• Transition table
q2 q2 q2
q1 q1 q2
q0 q1 q0
0 1
states
symbols
Example #2
Clamping Logic:
◼ A clamping circuit waits for a ”1” input, and turns on
forever. However, to avoid clamping on spurious noise,
we’ll design a DFA that waits for two consecutive 1s in a
row before clamping on.
◼ Build a DFA for the following language:
L = { w | w is a bit string which contains the
substring 11}
◼ State Design:
◼ q0
: start state (initially off), also means the most recent
input was not a 1
◼ q1
: has never seen 11 but the most recent input was a 1
◼ q2
: has seen 11 at least once
◼ Example #3
◼ Build a DFA for the following language:
L = { w | w is a binary string that has even number of 1s
and even number of 0s}
14
Extension of transitions to paths
◼ δ (q, w) = destination state from
state q on input string w.
◼ δ (q, wa) = δ (δ(q, w), a)
◼ Work out example #3 using the
input sequence w = 10010, a = 1:
◼ δ (q0
, wa) = ?
15
Language of a DFA
A DFA A accepts string w if there is a path from
q0
to an accepting (or final) state that is
labeled by w.
◼ i.e., L(A) = { w | δ(q0
,w)  F }
◼ i.e., L(A) = all strings that lead to an accepting
state from q0.
16
• Non-Deterministic Finite Automaton
Non-deterministic Finite Automata (NFA)
◼ A Non-deterministic Finite Automaton (NFA) is
called non-deterministic because the machine can
exist in more than one state at the same time.
◼ Transitions could be non-deterministic
◼ Each transition function therefore maps to a set of
states.
18
qi
1
1
qj
qk
…
Non-deterministic Finite Automata (NFA)
◼ An NFA consists of:
◼ Q = A finite set of states
◼ ∑ = A finite set of input symbols (alphabet)
◼ q0 = A start state
◼ F = Set of accepting states
◼ δ = A transition function, which is a mapping
between Q x ∑ → subset of Q
◼ An NFA is also defined by the 5-tuple:
◼ {Q, ∑ , q0
, F, δ }
19
How to use an NFA?
◼ Input: a word w in ∑
◼ Question: Is w accepted by the NFA?
◼ Steps:
◼ Start at the start state q0
◼ For every input symbol in the word w do
◼ Determine all possible next states from all current states,
given the current input symbol in w and the transition
function
◼ If after all symbols in w are consumed and if at least one of
the current states is a final state then accept w;
◼ Otherwise, reject w.
20
NFA for strings containing 01
21
q0
start
q1
0
0,1 0,1
1
q2
Final
state
• Q = {q0
,q1
,q2
}
•  = {0,1}
• start state = q0
• F = {q2
}
• Transition table
{q2
{q } 2 *q } 2
{q2 q Φ } 1
{q0
{q } 0
,q1 q } 0
0 1
states
symbols
What is an “error state”?
◼ A DFA for recognizing the key word “price”
◼ An NFA for the same purpose:
◼ Transitions into a dead state are implicit
22
q0
p
q1
r
q2
i
q3
c
q4
e
q5
qe
Any other input symbol
q0
p
q1
r
q2
i
q3
c
q4
e
q5
Any symbol
Example #3
◼ Build an NFA for the following language:
L = { w | w ends in 01}
◼ ?
◼ Other examples
◼ Keyword recognizer (e.g., if, then, else, while,
for, include, etc.)
◼ Strings where the first symbol is present
somewhere later on at least once
23
Extension of δ to NFA Paths
◼ Basis: δ (q, ) = {q}
◼ Induction:
◼ Let δ (q0
, w) = {p1
, p2…, pk
}
◼ δ (pi
, a) = Si for I =1, 2..., k
◼ Then, δ (q0
, wa) = S1 U S2 U … U Sk
24
Language of an NFA
◼ An NFA accepts w if there exists at least one
path from the start state to an accepting (or
final) state that is labeled by w
◼ L(N) = { w | δ(q0
, w) ∩ F ≠ Φ }
25
Differences between NFA and DFA
◼ DFA

1. All transitions are
   deterministic
   ◼ Each transition leads to
   exactly one state


2. For each state, transition on
   all possible symbols
   (alphabet) should be defined


3. Accepts input if the last state
   visited is in F


4. Harder to construct because
   of the number of states


5. Practical implementation is
   feasible
   ◼ NFA


6. Some transitions could be nondeterministic
   ◼ A transition may lead to a
   more than one state


7. Not all symbol transitions need to
   be defined explicitly (if undefined
   will go to an error state – this is
   just a design convenience, not to
   be confused with “nondeterminism”)


8. Accepts input if one of the last
   states is in F


9. Generally easier than a DFA to
   construct


10. Practical implementations limited
    but emerging (e.g., Micron
    automata processor)
    26
    Note: NFAs and DFAs are equivalent in power to recognize languages.
    Equivalence of DFA & NFA
    ◼ Theorem:
    ◼ A language L is accepted by a DFA if and only if it is
    accepted by an NFA.
    ◼ Proof:


11. If part:
    ◼ Prove by showing every NFA can be converted to an
    equivalent DFA.


12. Only-if part is trivial:
    ◼ Every DFA is a special case of an NFA where each state
    has exactly one transition for every input symbol.
    Therefore, if L is accepted by a DFA, it is accepted by a
    corresponding NFA.
    27
    Proof for the if-part
    ◼ If-part: A language L is accepted by a DFA if it is
    accepted by an NFA
    ◼ rephrasing…
    ◼ Given any NFA N, we can construct a DFA D such
    that L(N) = L(D)
    ◼ How to convert an NFA into a DFA?
    ◼ Observation: In an NFA, each transition maps to a subset
    of states
    ◼ Idea: Represent:
    Each “subset of NFA_states” ➔ a single “DFA_state”
    28
    NFA to DFA by subset construction
    ◼ Let N = {QN
    , ∑, δN
    , q0
    , FN
    }
    ◼ Goal: Build D = {QD
    , ∑, δD
    , {q0
    }, FD
    } s.t. L(D) = L(N)
    ◼ Construction:


13. QD = all subsets of QN
    (The power set of QN
    )


14. FD = set of subsets S of QN
    s.t. S∩FN ≠ Φ


15. δD = for each subset S of QN
    and for each input symbol
    a in ∑:
    ◼ δD
    (S, a) = U δN
    (p, a)
    29
    NFA to DFA construction: Example
    ◼ L = {w | w ends in 01}
    30
    q0 q1
    0
    0,1
    q2
    1
    NFA:
    δN 0 1
    q0
    {q0
    ,q1
    } {q0
    }
    q1 Ø {q2
    }
    *q2 Ø Ø
    DFA:
    δD 0 1
    Ø Ø Ø
    [q0
    ] {q0
    ,q1
    } {q0
    }
    [q1
    ] Ø {q2
    }
    *[q2
    ] Ø Ø
    [q0
    ,q1
    ] {q0
    ,q1
    } {q0
    ,q2
    }
    *[q0
    ,q2
    ] {q0
    ,q1
    } {q0
    }
    *[q1
    ,q2
    ] Ø {q2
    }
    *[q0
    ,q1
    ,q2
    ] {q0
    ,q1
    } {q0
    ,q2
    }
    δD 0 1
    [q0
    ] [q0
    ,q1
    ] [q0
    ]
    [q0
    ,q1
    ] [q0
    ,q1
    ] [q0
    ,q2
    ]
    *[q0
    ,q2
    ] [q0
    ,q1
    ] [q0
    ]


16. Enumerate all possible subsets


17. Determine transitions


18. Retain only those states
    reachable from {q0
    }
    [q0
    ]
    1
    0
    [q0
    ,q1
    ]
    1
    [q0
    ,q2
    ]
    0
    0
    1
    NFA to DFA
    ◼ L = {w | w ends in 01}
    ◼ Idea: To avoid enumerating each member of power set, do “lazy creation
    of states”.
    31
    q0 q1
    0
    0,1
    q2
    1
    NFA:
    δN 0 1
    q0
    {q0
    ,q1
    } {q0
    }
    q1 Ø {q2
    }
    *q2 Ø Ø
    DFA:
    δD 0 1
    [q0
    ] [q0
    ,q1
    ] [q0
    ]
    [q0
    ,q1
    ] [q0
    ,q1
    ] [q0
    ,q2
    ]
    *[q0
    ,q2
    ] [q0
    ,q1
    ] [q0
    ]
    [q0
    ]
    1
    0
    [q0
    ,q1
    ]
    1
    [q0
    ,q2
    ]
    0
    0
    1
    Correctness of subset construction
    Theorem: If D is the DFA constructed from NFA N by
    subset construction, then L(D) = L(N)
    ◼ Proof:
    ◼ Show that δD
    ({q0
    }, w) ≡ δN
    (q0
    , w} , for all w
    ◼ Using induction on w’s length:
    ◼ Let w = xa
    ◼ δD
    ({q0
    }, xa) ≡ δD
    ( δN
    (q0
    , x}, a ) ≡ δN
    (q0
    , w}
    32
    A bad case where #states(DFA) #states(NFA)
    ◼ L = {w | w is a binary string such that, the k
    th
    symbol from its end is a 1}
    ◼ NFA has k+1 states
    ◼ But an equivalent DFA needs to have at least 2
    k
    states
    (Pigeon hole principle)
    ◼ m holes and >m pigeons
    => at least one hole has to contain two or more pigeons
    33
    • An application: Text Search
    Applications
    ◼ Text indexing
    ◼ inverted indexing
    ◼ For each unique word in the database, store
    all locations that contain it using an NFA or a
    DFA
    ◼ Find pattern P in text T
    ◼ Example: Google querying
    ◼ Extensions of this idea:
    ◼ PATRICIA tree, suffix tree
    35
    Advantages & Caveats for NFA
    ◼ Great for modeling regular expressions
    ◼ String processing - e.g., grep, lexical analyzer
    ◼ Could a non-deterministic state machine be
    implemented in practice?
    ◼ Probabilistic models could be viewed as extensions of nondeterministic state machines
    (e.g., toss of a coin, a roll of dice)
    ◼ They are not the same though
    ◼ A parallel computer could exist in multiple “states” at the same
    time
    36
    A few properties of DFAs and NFAs
    ◼ The machine never really terminates.
    ◼ It is always waiting for the next input symbol or making
    transitions.
    ◼ The machine decides when to consume the next symbol from
    the input and when to ignore it.
    ◼ (but the machine can never skip a symbol)
    ◼ => A transition can happen even without really consuming an
    input symbol (think of consuming  as a free token) – if this
    happens, then it becomes an -NFA (see next few slides).
    ◼ A single transition cannot consume more than one (non-)
    symbol.
    37
    • Finite Automata with Epsilon Transitions
    NFA with -Transitions
    ◼ We can allow explicit -transitions in finite automata
    ◼ i.e., a transition from one state to another state without
    consuming any additional input symbol
    ◼ Explicit -transitions between different states introduce
    non-determinism.
    ◼ Makes it easier sometimes to construct NFAs.
    Definition: -NFAs are those NFAs with at least one
    explicit -transition defined.
    ◼ -NFAs have one more column in their transition
    table
    39
    Example of an -NFA
    ◼ -closure of a state q,
    ECLOSE(q), is the set of
    all states (including
    itself) that can be
    reached from q by
    repeatedly making an
    arbitrary number of -
    transitions.
    40
    L = {w | w is either empty or end in 01}
    δE 0 1 
    *q’0 Ø Ø {q’0
    ,q0
    }
    q0
    {q0
    ,q1
    } {q0
    } {q0
    }
    q1 Ø {q2
    } {q1
    }
    *q2 Ø Ø {q2
    }
    ECLOSE(q’0
    )
    ECLOSE(q0
    )
    start
    q0 q1
    0
    0,1
    1
    q2
    ECLOSE(q1
    )
    ECLOSE(q2
    )
    q’
    0
    
    -NFA Example-1
    Simulate for w = 101
    41
    L = {w | w is either empty or will end in 01}
    To simulate any transition:
    Step 1) Go to all immediate destination states.
    Step 2) From there go to all their -closure states as well.
    δE 0 1 
    *q’0 Ø Ø {q’0
    ,q0
    }
    q0
    {q0
    ,q1
    } {q0
    } {q0
    }
    q1 Ø {q2
    } {q1
    }
    *q2 Ø Ø {q2
    }
    ECLOSE(q’0
    )
    ECLOSE(q0
    )
    start
    q0 q1
    0
    0,1
    1
    q2
    q’
    0
     q0
    ’
    q0
    q0
    ’
     
    q1
    0
    q2
    1
    q0
    1
    Ø
    1
    x
    -NFA Example-2
    Simulate for w = 1001
    42
    δE 0 1 
    *q’0 Ø Ø {q’0
    ,q0
    ,q3
    }
    q0
    {q0
    ,q1
    } {q0
    } {q0,q3
    }
    q1 Ø {q2
    } {q1
    }
    *q2 Ø Ø {q2
    }
    q3 Ø {q2
    } {q3
    }
    start
    q0 q1
    0
    0,1
    1
    q2
    q’
    0
     
    q3
    1
    Equivalency of DFA, NFA, -NFA
    ◼ Theorem: A language L is accepted by some -NFA
    if and only if L is accepted by some DFA.
    ◼ Implication:
    ◼ DFA ≡ NFA ≡ -NFA
    ◼ (All accept Regular Languages)
    43
    Eliminating -transitions
    Let E = {QE
    , ∑,δE
    , q0
    , FE
    } be an -NFA
    Goal: To build DFA D = {QD
    , ∑, δD
    , {qD
    }, FD
    } such that L(D)=L(E)
    Construction:


19. QD = All reachable subsets of QE factoring in -closures


20. qD = ECLOSE(q0
    )


21. FD = Subsets S in QD
    s.t. S∩FE ≠ Φ


22. δD = For each subset S of QE
    and for each input symbol a∑:
    ◼ Let R = U δE
    (p, a) // go to destination states
    ◼ δD
    (S, a) = U ECLOSE(r) // from there, take a union of all their -closures
    44
    p in s
    r in R
    Example: -NFA to DFA (1)
    45
    L = {w | w is either empty or will end in 01}
    start
    q0 q1
    0
    0,1
    1
    q2
    q’
    0
    
    δE 0 1 
    *q’0 Ø Ø {q’0
    ,q0
    }
    q0
    {q0
    ,q1
    } {q0
    } {q0
    }
    q1 Ø {q2
    } {q1
    }
    *q2 Ø Ø {q2
    }
    δD 0 1
    *{q’0
    ,q0
    }
    …
    46
    start
    q0 q1
    0
    0,1
    1
    q2
    q’
    0
    
    δE 0 1 
    *q’0 Ø Ø {q’0
    ,q0
    }
    q0
    {q0
    ,q1
    } {q0
    } {q0
    }
    q1 Ø {q2
    } {q1
    }
    *q2 Ø Ø {q2
    }
    δD 0 1
    *{q’0
    ,q0
    } {q0
    ,q1
    } {q0
    }
    {q0
    ,q1
    } {q0
    ,q1
    } {q0
    ,q2
    }
    {q0
    } {q0
    ,q1
    } {q0
    }
    *{q0
    ,q2
    } {q0
    ,q1
    } {q0