My Youtube Video Channel ( With Theory of Computations)


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

  (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.


  1. how many transition is must from each state

  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.

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

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

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