24 Sep 2004 00:26:38 -0400

Related articles |
---|

generic state machine transaltion algorithm paulw@mmail.ath.cx (2004-09-21) |

Re: generic state machine transaltion algorithm cfc@shell01.TheWorld.com (Chris F Clark) (2004-09-24) |

Re: generic state machine transaltion algorithm wyderskiREMOVE@ii.uni.wroc.pl (Piotr Wyderski) (2004-10-02) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | 24 Sep 2004 00:26:38 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 04-09-126 |

Keywords: | lex |

Posted-Date: | 24 Sep 2004 00:26:38 EDT |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.