Re: generic state machine transaltion algorithm

Paul asked:


> [Is there a] generic algorithm for translating between state machines so
> that programs that used to run on one state machine can be run on
> another via this translation process?


I may not understand your question, so this may not be the answer you
want.


If I interpret your question theoretically, here is the answer:


Yes, there are algorithms for automatically translating state machine
programs from one "type" to another. For example, There are at least
two algorithms for automatically converting NFA (non-deterministic
finite state automata) to DFA (deterministic ones). There are also
algorithms to convert from regular expressions (one format of state
machine program) iinto NFA's, and to go from DFA's to regular
expressions, and also from linear grammars to regular expressions (and
back). Thus, if your program is in any one of those formats, you can
automatically convert it to another format.


In fact, when I took automata theory (ages ago) we were taught how to
convert a variety of different machines into and out of Turing
Machines--these conversions were all "automatic" (that is there were a
series of mechnical steps one performed to effect the translation) and
one of the homework assignments was to write our own conversion
process for a class of machines (I think it was from a Turing Machine
into FSA with queue). In any case, such algorithms are the basis of
many equivalency proofs.a


Now, is there an algorithm for taking an unspecified machine and
writing such a proof? That is, is there an algorithm for writing all
such algorithms? No, writing the proof requires "understanding" both
machines and how to model (simulate) the data storage of the one in
the other (or how to map problems from one into problems in the
other). In any case, the resulting proof is always mechanical.
However, writing the proof (developing the algorithm) is not.


If you mean something more practical, the answer is also "yes".


By practical, I presume you have some program in one machine language
and you want to run the program on another computer. Many
translators, cross-compilers, simulators, and emulators have been
written. There is even a story about how some 4 levels of emulation
were used to run some ancient program. I can't recall all the
machines involved, but I believe the end result was a IBM 370 machine
running a translation of a 7090 program that simulated a 1440, which
was running an emulation of 650. The 370 machine was, of course,
micro-coded, so even the "real" hardware was running a program written
for different hardware. In more recent history the FX32 project
allow(ed/s) one to run Intel x86 binaries on a VAX or Alpha.
Similarly, the Java virual machine is a model of an abstract machine
that is interpreted on a wide variety of platforms.


There has even been some work (much of it in the 80's) on generating
such translators automatically from "machine descriptions". However,
the success of those has mostly been in restricted domains
(i.e. "similar" machines of a given class).


I'm sorry if you had some more specific question in mind. It sounds
like you have a program that you want translated (or perhaps a
specific state machine model in mind), but the details beyond that
aren't clear (and even that is a guess on my part).


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Return to the comp.compilers page.
Search the comp.compilers archives again.