0
$\begingroup$

I am trying to figure out the process of generating code (set of instructions, implementation language specifics dont matter at this time) from an automaton.

The description of my intent is vague because although I am an electrical engineer, with extensive coding experience, I have no theoretical CS background and I am struggling to even articulate what I mean. The issue at hand is related to a digital circuit that I am working with. At this point I am not even aware of what I need to start looking into. Another way of describing my intent is, say I got a transition model of a process with the data requirements that are associated with the states. Knowing that, can I generate a program that will implement that model? Is there a field of study that deals with problems like this? Or should I just develop some logic to solve a limited interpretation of the model?

I believe I am using incorrect or misleading terms from a CS standpoint but I will appreciate if I can get some guidance on how to formulate my intent and then try to understand the possible solutions, if any.

Thanks!

$\endgroup$
1
$\begingroup$

A simple way to do it is to just write an interpreter that follows the transition table. I.e., do something like (in C):

state = INITIAL;
symbol = get_next();
while(symbol != END) {
   state = table[state][symbol];
   symbol = get_next();
}
if(is_accepting(state))
   /* Accept */

Next simpler is to write a rat's nest of gotos, transferring among them according to the symbol at hand (each label in the program corresponds to a state of the automaton).

Writing a decently organized,structured program from an automaton is possible, but far from automatic (and it would take a fair amount of work to check it really is faithful to the automaton).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Writing custom logic directed at the one machine I have at hand right now is definitely an option and in my wheelhouse of design automation scripting. I am also interested in knowing the pieces involved in "structured program from an automaton is possible" and "check it really is faithful to the automaton". These must be solved problems or studied at least in the CS domain? Are they? I may not end up doing all that is required but want to make a more educated decision on the path I end up taking. Thanks again. $\endgroup$ – Abhishek Bhaduri Jan 14 at 16:57
  • $\begingroup$ Probably the most efficient strategy is the goto one, the most flexible the transition table. Writing a structured program for any tangle of an automaton is possible in principle, but probably not worth the hassle (translating arbitrary transfers of control into a nice structure -- for some non-trivial value of "nice" -- is a lot of work, and making sure both check out even more so). Take a peek at a favorite of mine, Knuth's "Structured programming with goto statements" (and some of the many, many references) to see what this entails. So yes, it is studied; but rarely done in practice. $\endgroup$ – vonbrand Jan 14 at 17:07

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.