Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
2  
You may find some of our reference questions useful. Also, there is an actual algorithm for converting regular expressions to finite automata. I recommend to give the lecture (and you) some time and do the appointed exercise problems. –  Raphael Apr 12 at 9:40

3 Answers 3

up vote 0 down vote accepted

Yes there are rules to draw a DFA.

The first step is to draw a NFA (Non deterministic finite automaton), if we cannot draw instantly a DFA. We humans cannot with ease draw a DFA, especially for a complex language as you've seen. So we draw a NFA which is closer to our understanding. Then, rules are applied on the NFA in order to transform it into DFA. You will see that later on class.

Generally, in order to draw a NFA maybe we will use (only) a bit our imagination. With a given language, we firstly have to understand what is doing and after that we can start drawing pieces of the puzzle.

share|improve this answer
    
Thank you very much. I hope I will then be in a better state to do it when I have learnt about NFA. –  Zarah Apr 12 at 11:48
    
"We humans cannot with ease draw a DFA" -- if humans can't draw then who can draw? :) –  Grijesh Chauhan Apr 12 at 12:19
    
:) Sorry for the induction. Ι should've stated that I cannot draw a DFA of a complex Language without making a mistake. But I can with the algorithms :D. Human resourcefulness for the win! –  gon1332 Apr 12 at 12:32

Do not confuse defining an automaton and drawing an automaton.

The drawing is intended as a support for better intuition, and because it can often be read more easily in a single look. That is what drawing are usually for.

However, you are supposed to actually (be able to) give a formal definition, with the mathematical notation you learned, including specifying the transitions (not necessarily one by one).

In your example you could say, after specifying the transitions for the accepted string: this is completed by all transitions on terminals not yet considered in each state, each going to $q_{die}$, and all transitions on $q_{die}$ going back to it. Even this can be said more formally.

It is up to you, and to your instructor, to decide on the proper level of formalism. A drawing is usually enough in simple cases, as it is clear how to get the formal mathematical definition from it.

But for some more abstract problems, drawings are inconvenient, and the mathematical notation is much more easily used. Up to you to decide.

Constructing the automaton, as drawing or as math definition, depends on the problem at hand. There are many way, and your problem may often be to find the right one. Much of your course will be to teach you ways of building automata. These are only early and very simple exercises.

One point worth remembering. In order not to clutter drawings or descriptions, the state $q_{die}$ (or some equivalent states) is often onitted, as well as all transitions leading only to it (the reader is supposed to complete as I explained above). This is convenient, but dangerous ... some constructions or reasonnings based on automata rely on the fact that all transitions are taken into consideration ... and you may forget those that do not show explicitly.

share|improve this answer
    
Thank you very much for the comprehensive answer. I will upvote it as soon as I get a reputation of 15. –  Zarah Apr 12 at 11:51

The answer to your first question is YES for regular languages: there are indeed some algorithms to compute a DFA for a given regular Language. These algorithms should be given in the future lessons of your course.

Or we just have to imagine and think in our mind and get to a solution which satisfies the given Language?

You can just apply one of the algorithms (or use a computer to do it for you). However, for simple cases, you can sometimes guess the solution by yourself, but this needs practice.

share|improve this answer
    
Whether there is an algorithm depends on how the language is given. –  Raphael Apr 12 at 9:41
    
@Raphael You're right of course, but I did not want to enter into that. Remember the PO just got her first course on automata... –  J.-E. Pin Apr 12 at 9:44
    
Exactly; we should not give the expression that any description, however informal, can be translated in a structured way. It does not matter which formal representation you start with on your way towards an automaton, but you need to come up with one on your own. –  Raphael Apr 12 at 9:45
    
Thank you very much, I will upvote it as soon as I get a reputation of 15. I will be looking forward to future lessons to learn the algorithms, as I wouldn't be able to draw it (although it is simple but it is new) if the answer wasn't already there. –  Zarah Apr 12 at 11:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.