Search code examples
computer-sciencefinite-automatacomputation-theorycompiler-construction

Can anybody explain it to me in detail how to draw transition diagram (DFA/NFA) in theory of computer science?

Ok so this subject is little confusing. I can understand the transition table very well but when it comes to diagram I'm struggling to find out on what basis the diagram is created. Can anybody explain it to me in detail on what basis do we have to construct Transition diagram of Dfa and Nfa's.

Solution

  • You have to just perform if-elseif type conditions to draw the DFA from table.

    DFA: i.e Deterministic Finite Automata in which decision for any input should be deterministic i.e. there should be confirmation about output on particular input. So it has only one state as output for particular input.

    NFA: i.e Non-Deterministic Finite Automata in which decision for any input may not be deterministic i.e. there may not be confirmation about output on particular input. So it can have one or more states as output for particular input.

    • Let's take an example for constructing DFA diagram:

    Suppose you have transition table given as:

    Transition Table

    The → indicates the start state: here q0

    The ∗ indicates the final state(s) (here only one final state q1)

    The DFA diagram for this table would be:

    DFA

    Explanation:

    • From table, it is clear that from starting state i.e. A, when you get symbol 0 as input then you have to go to state C, and when you get symbol 1 as input then you have to go to state B.

      So in diagram, we show arrows between two states according to the symbol.

    • Like this, we move to B, and table shows that on symbol 0 as input, go to state C and on symbol 1 as input, go to state B. So you draw two arrows according to this.

    • From C, on symbol 0 as input go to state C, and on symbol 1 as input go to state D i.e. final state. So you draw two arrows for this.

    • Again same process is done for D.

    NOTE: For showing a state as initial state, you add an arrow behind the circle denoting the first state, and for denoting the state as final state, you draw a circle inside other as shown in the figure.

    • Let's take another example for constructing NFA diagram:

    Suppose you have transition table given as:

    T_table for NFA

    The NFA diagram for table can be constructed as:

    enter image description here

    You can easily understand the concept, as concept here is same as DFA diagram construction. The difference here would be that, on single input, there can be multiple output states; so you have to draw arrow for each of the output states.

    DFA for strings that starts with 0 and ends with 1:

    DFA_EXample

    Construction:

    1. Draw an initial state circle 1.

    2. As string should start with 0, so, on getting a 0 as input, transition should go ahead with next state 2 as our first case is satisfying here. So make a new state circle 2 and show 0 as input on the arrow between both states.

      But the problem is, when you get input 1, then your both the cases (0 should be first input and 1 should be last) can never be satisfied now. So for it make another state 3 circle for input 1, and show an arrow to that state that goes to the same state 3 on input 1 and 0. As your conditions can never be satisfied now, so you leave your state 3 here by showing a loop to itself.

    3. Now let's move ahead to state 2. When you get input as 0, you have to show the loop to the state-2 itself, because your final condition i.e. "1 should be in the end of the string" is not satisfying on getting a 0 as input--> so you can't go to final state for this.

      But when you get input 1 on state-2, then you get your both the condition (0 should be first input and 1 should be last), are satisfying. So you make the arrow to the final state-4 for input 1 on state-2.

    4. Now on final state i.e. state-4, you can still get input as there is not any length given of the string. So you can still get inputs 1 and 0.

      • When you get input as 1 on final state, then your string would be now something like 011 so your both the condition are satisfying now, so you make a loop to the final state on input 1.

      • But when you get input as 0 on final state i.e. state-4 then your string would be something like 010 then your one condition i.e. "1 should be the last element of the string" is not satisfying then you make a transition from state-4 to state-3 as that's the only state which can solve the problem of getting 1 in the end of the string.

    Hope you understand the concept now and it help you!