CODEWITHSUNDEEP
finite-automatadfaautomata
Solace
Solace

Reputation: 9020

Are there any steps or rules to draw a DFA?

In my first lecture of "Theory of Automata", after giving some concepts of Alphabet, Language, transition function etc. and a couple of simple automata of an electric circuit with one and two switches, is this question.

enter image description here

I understand what an Alphabet as well as the Language of a DFA is, but are there any rules or steps to followed to reach a correct automaton for a given Language? Or we just have to imagine and think in our mind and get to a solution which satisfies the given Language?

Note:- Please keep your language as simple as you can, since this is my first lecture and I am not yet aware of concepts like regular expressions or any other thing in the subject for that matter.

Upvotes: 2

Views: 10155

Answers (3)

Weird Box
Weird Box

Reputation: 11

Steps To Construct DFA-

Following steps are followed to construct a DFA for Type-01 problems-

Step-01: Determine the minimum number of states required in the DFA. Draw those states.

Step-02: Decide the strings for which DFA will be constructed.

Step-03: Construct a DFA for the strings decided in Step-02.

Step-04: Send all the left possible combinations to the starting state. Do not send the left possible combinations over the dead state.

Upvotes: 0

Siddian
Siddian

Reputation: 11

I am a novice .. but as per my experience.. the boundary conditions of the language to be accepted should be drawn 1st and then the complexities can be added while looking at the conditions which will get rejected step by step ... as a start if the figure in the question would have been for a DFA which accepts L={01*0}, then the bare minimum string would be "010" ..and eventually the dfa can be constructed keeping in mind the trap states and some analysis Hope this helps !!

Upvotes: 1

sdwaraki
sdwaraki

Reputation: 412

If you are given a description of the language in words, say, think about all the possible strings that can apply to this language. Then, try to come up with a DFA that handles most of the strings. Then look into the boundary conditions and generate some strings. Try to accommodate it in the DFA. This might be a good starting point for you

http://www.cse.chalmers.se/~coquand/AUTOMATA/o2.pdf

Upvotes: 2

Related Questions