Sun, 16 Aug 2009 20:36:58 +0100

Related articles |
---|

Automata terminology - mixed input and output event transitions, trans sh006d3592@blueyonder.co.uk (Stephen Horne) (2009-08-16) |

Re: Automata terminology - mixed input and output event transitions, t cfc@shell01.TheWorld.com (Chris F Clark) (2009-08-30) |

Re: Automata terminology - mixed input and output event transitions, t sh006d3592@blueyonder.co.uk (Stephen Horne) (2009-08-31) |

Re: Automata terminology - mixed input and output event transitions, t cfc@shell01.TheWorld.com (Chris F Clark) (2009-09-01) |

From: | Stephen Horne <sh006d3592@blueyonder.co.uk> |

Newsgroups: | comp.compilers |

Date: | Sun, 16 Aug 2009 20:36:58 +0100 |

Organization: | virginmedia.com |

Keywords: | theory, question |

Posted-Date: | 16 Aug 2009 17:49:59 EDT |

I'm currently working on a problem using finite automata where each

transition represents either an input event or an output event. In a

deterministic example, a state would either have a single outward

output transition or any number of outward input transitions. The

first case is a "transient" state - the machine doesn't wait for an

input in that state, it just follows the output event transition

immediately, generating the output event as it does so.

Rather obviously, there is always an alternative representation which

describes an equivalent automaton. In this representation, there are

no transient states. Each transition is annotated with one input event

and a regular grammar/finite automaton representing the possible

output sequences. If the original model is deterministic, all these

output grammars will be simple sequences of output events.

In this second form, if you strip off all the output annotations, you

get a finite automaton that describes the grammar for input events,

ignoring output issues. If there are no output events, the two forms

are identical.

The interesting point about this is that some composition operators

make more sense in the first form whereas others make more sense in

the second. For example, a simple union operator will be very prone to

creating nondeterminism using the first form - good for modelling

concurrent outputs, but in my application, not very useful. But using

the second form there are alternative unions which are standard unions

WRT input events, but which select/combine the output grammars

differently. What I think of as the "else" union and the "then" union

are essential examples in my application.

It is useful, therefore, to be able to translate from one form to the

other, with the translation from the first form to the second

(allowing nondeterminism) being a bit fiddly though conceptually

simple enough once you get the idea.

Anyway, I find it extremely hard to believe that I'm inventing this,

but I don't remember reading anything in any theory books or papers.

What I'm particularly concerned about is terminology, so that my

source code and documentation is readable.

I think I picked up the term "transient state" from hardware stuff,

many many years ago - but what is the normal non-transient state

called? "Non-transient" and "intransient" seem clunky. "Normal state"

is too context sensitive - normal relative to what, basically.

"Waiting state" just seems wrong - too close to "wait state" in the

memory sense, I guess.

More importantly, are there standard names for the two different

representations? Using terms like "the one with transient states" is

nuts. If there are standard names along the lines of "Fred machine"

and "Barney machine" or whatever, that would be great. I very much

doubt that I can claim the naming priviledge.

The terms "Moore machine" and "Mealy machine" are tempting but wrong.

There are superficial similarities between these and the forms I'm

using, but the concepts simply don't match.

Finally, if anyone can point me to any interesting theory papers along

the same lines, I'd be more than curious. I can't seem to find much

via Google - probably because I don't know the right words to search

for.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.