1

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.

Solace
  • 8,612
  • 22
  • 95
  • 183
  • 1
    Simple language: this is not a programming problem. You should ask on [cs.se] –  Apr 12 '14 at 07:31
  • @MikeW OK thank you. I just added it here because I saw some similar questions here. – Solace Apr 12 '14 at 07:34
  • 1
    Zarah: There is no formal rule to draw DFAs from English description, it is more like matter of aptitude. You can only learn it by practice, like you learn programming. Start with simpler examples given in your book, you will learn some tricks. Keep remember those solutions and trick...that is the ways. – Grijesh Chauhan Apr 12 '14 at 11:50
  • @GrijeshChauhan But some 3 people just said that there are some algorithms. Please check it [here](http://cs.stackexchange.com/questions/23694/are-there-any-steps-or-rules-to-draw-a-dfa?noredirect=1#comment47219_23694) – Solace Apr 12 '14 at 11:56
  • 1
    @Zarah You didn't got it. What they are answering is: "convent from one representation to other" for example if you have RE (regular expression) or NFA (non-determinitic finite automata) then you have algorithmic methods to convent them into DFA. But What I means if you are given "English description of language" -- – Grijesh Chauhan Apr 12 '14 at 12:00
  • Anyways to come up with any one representation RE, NFA, DFA from English description is need aptitude. – Grijesh Chauhan Apr 12 '14 at 12:05
  • @GrijeshChauhan You were right. Actually now I see that the example I posted is indeed very simple, but that was the first lecture... You were right, and thank you. – Solace Jun 04 '14 at 07:15
  • @Zarah There are many questions I answered to teach How to approach answers to such questions For an example read this one ["Proving a Certain Language Regular"](http://stackoverflow.com/questions/22030410/proving-a-certain-language-regular?lq=1) some answers I linked to that answer, some answer I linked in my profile page. Hope you find them helpful. – Grijesh Chauhan Jun 04 '14 at 09:40

3 Answers3

1

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

sdwaraki
  • 382
  • 1
  • 4
  • 12
1

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

Siddian
  • 11
  • 1
0

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.

Weird Box
  • 11
  • 1