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

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)