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

While your automata are not unique, and I've seen others use such a
model (in fact I use a very similar model in the FA's I use in my
current security work), I don't recall them ever being named.


Still, I'm quite certain I've seen this model described somewhere in
introductory material on implementing state machines in an OO fashion.
The separation of the input and output nodes map naturally onto ways
one would want to parameterize the model. That is there are a lot of
places where you would like a common state machine (the input edges
and states), but be able to customize the outputs--having separate
edges for them allows just that and you can in objected oriented
fashion describe a variety of translators simply by varying what the
output edges do. Hmmm, thinking of it that way, I'd be surprised if
there isn't a pattern name for that, like decorator.


One question. Do you have epsilon transitions (transitions with no
input and no output) in your machine? Or, must every transition be
marked with an input or an output? If you have epsilon transitions, I
believe your automata are simply a constrained form of NFAs, but with
no exceptional properties, i.e. for any "standard" NFA, one can
construct an equivalent automaton with your restrictions and obviously
vice versa. If you don't allow epsilon transitions, then your machine
is non-standard, and may have interesting properties, whether the
properties are useful is not clear.


And, I agree that the temptation to associate the restrictions in your
model somehow with Moore machines, but that's only because a Moore
state is simply modelled in your automata as a pair of states with an
output transition between them. A Mealy edge is the same way, it is
a pair of edges, one with an input and one with an output with a state
between them.


Coming from a parsing background, I would tend to call the states with
input labeled eges, as "shift target" states, as a transition (edge,
arrow) marked with an input is a "shift transition" in LR parlance.
However, I don't think that nomenclature is at all standard nor useful
in something like a Google search.


Hope this helps,
-Chris


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

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