Automata terminology - mixed input and output event transitions, transient states

Stephen Horne <sh006d3592@blueyonder.co.uk>
Sun, 16 Aug 2009 20:36:58 +0100

          From comp.compilers

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)
| List of all articles for this month |

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.