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

On Sun, 30 Aug 2009 18:42:33 -0400, Chris F Clark
<cfc@shell01.TheWorld.com> wrote:


>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.


Interesting that you mention security work. Thinking about it, while I
happen to be writing a DSL, this approach seems more suited to network
protocols than to any traditional compiler problem.


>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?


I have epsilon transitions, but only in intermediate stuff. The final
results are required to be deterministic. If I can't eliminate all
epsilons, it's an error.


When dealing with the model where you have edges for inputs only, but
annotated with the full output as well as the input, a few transitions
may be needed for initial outputs that preceed the first input event.
These obviously look like epsilons from the input perspective, but the
output annotation is important. And for determinism, of course, there
can only be one of these with a simple-sequence output, leading from a
single transient start state.


> 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.


They can definitely be represented as standard automata, in which
every input or output event is simply considered an event. This is
exactly how they are represented most of the time, simply because it
allows me to do most things with existing code.


In this form, the only oddities are some extra constraints on what is
considered deterministic and a small set of operators (union,
intersection, and symmetric and asymmetric differences) that don't do
what I mean, because I naturally want to define those operators in
terms of input events only, yet keep the outputs consistent in the
result.


My ad-hoc terms for the moment are...


- Input model - models input events only


- Output model - models output events only


- Event model - every event, input or output, gets a separate
    transition.


- Reaction model - very similar to input model, but each input
    transition is annotated with a small output state model (in the
    deterministic case, a simple sequence of output events).


The "program" translates from an input (consistent with the input
model) to an output (consistent with the output model). The program
can be represented using either the event model or the reaction model.


> 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.


It's definitely useful, at least to me - but I don't think it has any
theoretical value. As stated above, the conversion to reaction model
from event model is very similar to converting to an input model -
you're essentially stripping out the output events. Apart from a few
technicalities, the only real difference is that you preserve that
information as annotations on the input transitions.


>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.


I don't know. If I start thinking of input events as "shifts", then
what are the output events? They certainly aren't reduces.


Also, in the event model, I tend to focus more on the transitions
leaving the state to characterise that state - e.g. transient states
being those that have outward output transitions, because there is no
waiting around for another input. I guess I'll just have to call those
with outward input transitions "waiting" states.

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