Popular Posts

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.


Visitor's Feedback

"I am very thankful, providing good stuff for engg students. I got good information about TOC and its information valuable for me."
: - Ankur Loriya (Ahmedabad)

"An amazing work, i just love your work!! please please please keep updating application based problems as well, it will definitely add interests to those whose visit your blog!! Thank you"
: - Preethi Velmurughan (Coimbatore)

"I got chance to learn what is the theory of computation thats why thankh you very much for this blog"
: - Ajay Sapkota (Kathmandu)

"Very nice presentation ,easy to go through the content"
: - Dr. A ramesh babu(Trichy)

"Nice tutorial example of constructing dfa..... thanks"
: - Manoj kumar (Delhi)

"I am a lecturer who is handling TOC for B.E students ....This is blog is very much useful for me ..It gives a lot of informations."
: - Sivaranjani.s (Theni)

"This is very good material for theory of computation thank you sir"
: - Mohan lal jat (Udaipur)

"its very good for engg student to get a readymade questions at the exam time. thank you."
: - Asfiya Peerjade (Kolhapur)

"I am a lecturer....this blog is awussom for me to understand.... and to learn more practical example....thanx nd plzzzz update more 1"
: - Sumedha Bhagat (Lecturer, Pune)

"You are doing very good job for an engg student for getting more problems with solution."
: - Chandrakant (Student, Nanded)

Google+ Followers