Search code examples
finite-automataregular-languageautomatadfa

How to solve δ(A,01) for this DFA?

enter image description here Consider the DFA :

What will be δ(A,01) equal to ? options:

A) {D}    
B) {C,D}      
C) {B,C,D}       
D) {A,B,C,D}

The correct answer is option B) but I don't get how. Please some one explain me the steps to solve it and also in general how do we solve sit for any DFA and any transition?

Thanks.

Solution

  • B) Option is not Correct answer! for this transition graph.

    In Transition Graph(TG) symbol ε means NULL-move (ε-move). There is two NULL-moves in TG. 

    One:       (A) --- `ε` ---->(B)  
Second:    (A) --- `ε` ---->(C)

    A ε-move means without consume any symbol you can change state. In your diagram from A to B, or A to C.

    What will be δ(A,01) equal to ?

    Question asked "what is path from state A if input is 01". (as I understand because there is only one final state)

    01 can be processed in either of two ways.

    • (A) -- ε --->(B) -- 0 --> (B) -- 1 --> (D)

    • (A) -- ε --->(C) -- 0 --> (B) -- 1 --> (D)

    Also, there is no other way to process string 01 even if you don't wants to reach final state.

    [ANSWER]
    So there is misprinting in question (or either you did).

    You can learn how to remove NULL-move from transition graph. Also HOW TO WRITE REGULAR EXPRESSION FOR A DFA

    If you remove null-moves from TG you will get three ways to accept 01.

    TG

    EQUIVALENT TRANSITION GRAPH WITHOUT NULL-MOVE

    Note there is three start-states in Graph.

    Three ways: 

    {ABD}  
{CBD}  
{BBD}

    In all option state-(B) has to be come.

    Also, you have written Consider the DFA : is wrong. The TG is not deterministic because there is there is non-deterministic move δ(A,ε) and next states are either B or C.