| |
 |
|
| Computers Forum Index » Computer Compilers » Automata terminology - mixed input and output event... |
|
Page 1 of 1 |
|
| Author |
Message |
| Stephen Horne... |
 Posted: Mon Aug 31, 2009 7:26 am |
|
|
|
Guest
|
On Sun, 30 Aug 2009 18:42:33 -0400, Chris F Clark
<cfc at (no spam) shell01.TheWorld.com> wrote:
Quote: 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.
Quote: 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.
Quote: 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.
Quote: 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.
Quote: 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. |
|
|
| Back to top |
|
|
|
| Chris F Clark... |
| Posted: Tue Sep 01, 2009 10:39 am |
|
|
|
Guest
|
Quote: I guess I'll just have to call those
with outward input transitions "waiting" states.
How about "expecting", "pending", or "inconclusive" states? As in,
the state is expecting more input, there should be input pending, or
you haven't reached a conclusive input (that causes you to generate a
response). |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Sun Nov 22, 2009 4:09 pm
|
|