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.


3 Answers 3


Yes, there are procedures that help you draw a DFA.

One of them is to draw first an 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.

  • $\begingroup$ Thank you very much. I hope I will then be in a better state to do it when I have learnt about NFA. $\endgroup$
    – Solace
    Apr 12, 2014 at 11:48
  • $\begingroup$ "We humans cannot with ease draw a DFA" -- if humans can't draw then who can draw? :) $\endgroup$ Apr 12, 2014 at 12:19
  • $\begingroup$ :) 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! $\endgroup$
    – gon1332
    Apr 12, 2014 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.

  • $\begingroup$ Thank you very much for the comprehensive answer. I will upvote it as soon as I get a reputation of 15. $\endgroup$
    – Solace
    Apr 12, 2014 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.

  • $\begingroup$ Whether there is an algorithm depends on how the language is given. $\endgroup$
    – Raphael
    Apr 12, 2014 at 9:41
  • $\begingroup$ @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... $\endgroup$
    – J.-E. Pin
    Apr 12, 2014 at 9:44
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Apr 12, 2014 at 9:45
  • $\begingroup$ 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. $\endgroup$
    – Solace
    Apr 12, 2014 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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