My Youtube Video Channel ( With Theory of Computations)

Loading...

Friday, October 7, 2011

How to Draw DFA for Start with?

Steps for Drawing DFA.
Example:  Strings start with 011.

- Keep In Mind
  (1) There should be one Stuck/Dead State.
  (2) Stuck/Dead State should have self loop.(For all alphabets)
  (3) Final/Acceptance State should have self loop.(For all alphabets)

- Steps
  (1) Find out Minimum Length String in Language. (e.g 011).
  (2) Draw Minimum Length + 1 number of
states.


  (3) Mark
First state as Initial State.
  (4) Mark Last state as Final/Acceptance State.
 
  (5) Draw Transition for Minimum Length String.(011)
  (6) Draw
Self Loop for Final State.


  (7) Draw one
Isolated State with Self Loop. (Stuck/Dead State)


  (8) All
Remaining Transition attach to Stuck/Dead State.

DFA start with 011
"Now,Your DFA is complete" Check it.

5 comments:

  1. how many transition is must from each state

    ReplyDelete
  2. There are two types of transition.
    1) Incoming Transition (In-degree):
    - There is no rules for incoming transition.
    2) Outgoing Transition (Out-degree):
    - No. of outgoing Transition = No. of Alphabets in Language.
    - e.g. if set of alphabet in Language E={a,b,c} then there must be 3 outgoing transition for
    each state.

    ReplyDelete
  3. No. of outgoing Transition = No. of symbols in Alphabet

    ReplyDelete
  4. No of Symbol in Language.
    Symbol and Alphabet both are same.

    ReplyDelete
  5. Please draw a DFA which accepts the string over (a,b) where no of a is old and no of b is even.

    ReplyDelete