1
$\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!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\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).

Improve this answer
$\endgroup$
4
  • $\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$ Commented Jan 14, 2020 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$ Commented Jan 14, 2020 at 17:07
  • $\begingroup$ May I know why "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)" and why "it's rarely done in practice"? Does that mean automaton is not useful in practice (real coding)? $\endgroup$ Commented Sep 21, 2020 at 9:21
  • $\begingroup$ @kate, it is easier to just write out the rat's nest of goto automatically (that's what Thompson did in his first implememtations of regex searches, writing machine language directly). There is little to win by nicely structured code, it is more important that anybody can check that the code corresponds to the DFA, $\endgroup$ Commented Sep 21, 2020 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.