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

Welcome to Scribd!

  • 494 views

    DFA Minimization

    Uploaded by

    Anik
    The document discusses minimizing DFAs (deterministic finite automata). It begins with a larger 5-state DFA that accepts strings ending in 111. It then asks if there is a smaller DFA. The document explains that by the pigeonhole principle, any 3-state DFA would result in two inputs ending in the same state, violating the language. Therefore, the given 5-state DFA is minimal. It then discusses the concept of distinguishable states and how merging indistinguishable states results in a minimal DFA.

    Copyright:

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

    DFA Minimization

    Uploaded by

    Anik
    494 views25 pages
    The document discusses minimizing DFAs (deterministic finite automata). It begins with a larger 5-state DFA that accepts strings ending in 111. It then asks if there is a smaller DFA. The document explains that by the pigeonhole principle, any 3-state DFA would result in two inputs ending in the same state, violating the language. Therefore, the given 5-state DFA is minimal. It then discusses the concept of distinguishable states and how merging indistinguishable states results in a minimal DFA.

    Original Description:

    Algorithm for minimizing DFA

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses minimizing DFAs (deterministic finite automata). It begins with a larger 5-state DFA that accepts strings ending in 111. It then asks if there is a smaller DFA. The document explains that by the pigeonhole principle, any 3-state DFA would result in two inputs ending in the same state, violating the language. Therefore, the given 5-state DFA is minimal. It then discusses the concept of distinguishable states and how merging indistinguishable states results in a minimal DFA.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    494 views25 pages

    DFA Minimization

    Uploaded by

    Anik
    The document discusses minimizing DFAs (deterministic finite automata). It begins with a larger 5-state DFA that accepts strings ending in 111. It then asks if there is a smaller DFA. The document explains that by the pigeonhole principle, any 3-state DFA would result in two inputs ending in the same state, violating the language. Therefore, the given 5-state DFA is minimal. It then discusses the concept of distinguishable states and how merging indistinguishable states results in a minimal DFA.

    Copyright:

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

    DFA minimization

    Example
    • Construct a DFA over alphabet {0, 1} that
    accepts those strings that end in 111 0
    0 q
    0 q 1
    1
    q q
    1
    0 q …

    …
    q
    1 q
    0 q
    1
    q …

    …
    1
    q 1
    q 1

    • This is big, isn’t there a smaller DFA for this?


    Smaller DFA

    0
    1 1 1
    q q q q 1
    0
    0

    Can we do it with 3 states?


    Even smaller DFA?
    • Suppose we had a 3 state DFA M for L

    … let’s imagine what happens when:

    M
    inputs:

    , 1, 11, 111

    • By the pigeonhole principle, on two of these


    inputs M ends in the same state
    Pigeonhole principle
    Suppose you are tossing m balls into n bins, and
    m > n. Then two balls end up in the same bin.

    • Here, balls are inputs, bins are states:

    If you have a DFA with n states and you run it on


    m inputs, and m > n, then two inputs end up in
    same state.
    A smaller DFA
    • Suppose M ends up in the same state after
    reading inputs x = 1 and y = 11
    M 1, 11
    inputs:

    , 1, 11, 111 11, 111

    “ends in 111”
    • Then after reading one more 1
    – The state of x1 = 11 should be rejecting
    – The state of y1 = 111 should be accepting
    … but they are both the same state!
    A smaller DFA
    • Suppose M ends up in the same state after
    reading inputs x =  and y = 1
    M , 1
    inputs:

    , 1, 11, 111 11, 111

    “ends in 111”
    • Then after reading 11
    – The state of x1 = 11 should be rejecting
    – The state of y1 = 111 should be accepting
    … but they are both the same state!
    No smaller DFA!
    • After looking at all possible pairs for x, y, x ≠ y
    (, 1) (, 11) (, 111) (1, 11) (1, 111) (11, 111)

    we conclude that
    There is no DFA with 3 states for L

    • So, this DFA is minimal


    0
    1 1 1
    q q q q 1
    0
    0

    0
    DFA minimization 0

    q  1
    0 q 
    1 1

    …
    q
    q  … q 
    1
    1

    …
    0 1
    q  … q
    1 q 
    1
    q q  1
    0 q
    0 q  0
    1
    1 0
    0 0
    q
    q 1 q

    We will show how to turn any DFA for L into the


    minimal DFA for L
    Minimal DFAs and distinguishable
    states
    • First, we have to understand minimal DFAs:
    reject accept
    0
    1 1 1
    q q q q 1
    0
    0

    every pair of states


    minimal DFA
    is distinguishable
    Distinguishable states
    • Two states q and q’ are distinguishable if
    p t
    w1 w2 wk-1 wk cce
    … a
    q

    c t
    w1 w2 wk-1 wk j e
    … re
    q’

    on the same continuation string w1w2...wk, one


    accepts, but the other rejects
    Examples of distinguishable states
    0 1 1

    1 0 1
    q q q q

    0
    0

    (q0, q1) distinguishable by 01


    (q0, q2) distinguishable by 1
    (q0, q3) distinguishable by  DFA is minimal
    (q1, q2) distinguishable by 1
    (q1, q3) distinguishable by 
    (q2, q3) distinguishable by 
    Examples of distinguishable states
    0 q q
    q 0
    0

    0, 1

    0, 1
    q0 1
    1
    q 1
    q 0, 1 q
    0, 1

    (q0, q3) distinguishable by 


    (q1, q3) distinguishable by 
    (q2, q3) distinguishable by  indistinguishable pairs
    (q1, q2) distinguishable by 0 can be merged
    (q0, q2) distinguishable by 0
    (q0, q1) indistinguishable
    Examples of distinguishable states
    0
    q q
    0, 1 0, 1
    q q
    1 0, 1
    q 0, 1 q

    0, 1

    (q0, q2) distinguishable by 


    (q1, q2) distinguishable by 
    (q0, q3) distinguishable by 
    (q1, q3) distinguishable by 
    (q0, q1) indistinguishable
    (q2, q3) indistinguishable
    Finding (in)distinguishable states
    If q is accepting and q’ is rejecting
    Rule 1: q x q’ Mark (q, q’) as distinguishable (x)

    q1 x q1 ’

    a a If (q1, q1’) are marked,


    Rule 2: Mark (q2, q2’) as distinguishable (x)
    q2 x q2 ’

    Unmarked pairs are indistinguishable


    Rule 3: Merge them together
    Example of DFA minimization
    0
    q
    0 q
    q q
    0 1 1
    q 0 q
    q 1 0 q
    1 0 q 1
    q 0 q
    1
    q q
    q q q q q q
    1
    Example of DFA minimization
    0
    q
    0 q
    q q
    0 1 1
    q 0 q
    q 1 0 q
    1 0 q 1
    q 0 q
    1
    q q x x x x x x
    q q q q q q
    1

     q11 is distinguishable from all other states


    Example of DFA minimization
    0
    q
    0 q
    q q x x
    0 1 1
    q 0 q x
    q 1 0 q
    1 0 q 1
    q 0 q x
    1
    q q x x x x x x
    q q q q q q
    1

     q1 is distinguishable from q, q0, q00, q10


    On transition 1, they go to distinguishable states
    Example of DFA minimization
    0
    q
    0 q
    q q x x
    0 1 1
    q 0 q x
    q 1 0 q x x x
    1 0 q 1
    q 0 q x x
    1
    q q x x x x x x
    q q q q q q
    1

     q01 is distinguishable from q, q0, q00, q10


    On transition 1, they go to distinguishable states
    Example of DFA minimization
    0
    q A
    0 q
    A q q x x
    0 1 1
    q 0 q A A x
    q 1 0 q x x B x
    1 0 q 1
    q 0 q A A x A x
    B 1
    q q x x x x x x
    C
    q q q q q q
    1

     Merge states not marked distinguishable


    q, q0, q00, q10 are equivalent → group A
    q1, q01 are equivalent → group B
    q11 cannot be merged → group C
    Example of DFA minimization
    0
    q A
    0 q
    q q x x
    A 0 1 1
    q 0 q A A x
    q 1 0 q x x B x
    1 0 q 1
    q 0 q A A x A x
    B 1
    q q x x x x x x
    C q q q q q q
    1

    0
    1 1
    minimized DFA: q q qC 1
    0
    0
    Food for thought
    • Why does method find all distinguishable pairs?

    w1 w2 wk-1 wk
    …
    q
    x x x x
    w1 w2 wk-1 wk
    …
    q’

    Because we work backwards


    Food for thought
    • Why are there no inconsistencies when we merge?
    B
    w
    q5
    a

    A q2
    q3
    q1
    q7
    a C
    w
    q6

    Because we only merge indistinguishable states


    Food for thought
    • Why is there no smaller DFA?
    Suppose there is

    By the pigeonhole principle this must happen:

    M smaller DFA M’
    v q
    q’’
    v, v’
    v’ q’
    Food for thought
    • Why is there no smaller DFA?
    But then
    M smaller DFA M’
    v q w
    q’’ w
    v, v’
    ?
    v’ q’ w

    Every pair of states q’’ cannot exist!


    is distinguishable

    You might also like