DFA illustration...

[Don Y]

In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\". But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation. Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state. This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state. Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

 

[Martin Rid]

jlarkin@highlandsniptechnology.com Wrote in message:r

On Thu, 8 Sep 2022 16:10:01 -0700, Don Y <blockedofcourse@foo.invalid>wrote:>In practical terms, one augments each transition with an>\"action\" associated with the input(s) being acted upon.>>In my software implementations, I employ several hacks>to increase efficiency and range of expression possible>in a given machine. (not worth explaining, here)>>In an example I\'m presently working, it would really be nice>to annotate the graphic representations of the machines with>some of these \"hacks\". But, they aren\'t consistent with>traditional DFA illustration practices (nor are the explicit>action annotations!) so I\'m at a loss as to an *intuitive*>means of annotation. Something that an observer unfamiliar>with the mechanism could easily infer without needing a legend!>>Chief among these, I impose (optional) \"on entry\" and \"on exit\">actions for each state. This is a shorthand to avoid having to add>those actions to every transition entering -- or exiting -- the>state.>>So, every transition entering the \"OFF\" state need not explicitly>\"remove_power()\" if an \"on entry\" action declared that action for>the OFF state. Otherwise, any transition arriving at OFF failing>to do so could resu
lt in the machine being in the OFF state without>having already *removed* power.>>Likewise, every transition leaving the OFF state (presumably for some>\"non-OFF\" state) can be assured to \"apply_power()\" by the specification>of that as an \"on exit\" action for the OFF state.>>DFA illustrations quickly become cluttered (esp if inputs are named>symbolically) so any mechanism has to be relatively \"tight\"...What is DFA?

I\'ll vote for \"Death From Above\"

Cheers
--


----Android NewsGroup Reader----
https://piaohong.s3-us-west-2.amazonaws.com/usenet/index.html

 

[Jeroen Belleman]

On 2022-09-09 04:41, jlarkin@highlandsniptechnology.com wrote:

On Thu, 8 Sep 2022 16:10:01 -0700, Don Y <blockedofcourse@foo.invalid
wrote:

In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\". But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation. Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state. This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state. Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

What is DFA?

Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Jeroen Belleman

 

[server]

On Fri, 09 Sep 2022 10:05:55 +0200, Jeroen Belleman
<jeroen@nospam.please> wrote:

On 2022-09-09 04:41, jlarkin@highlandsniptechnology.com wrote:
On Thu, 8 Sep 2022 16:10:01 -0700, Don Y <blockedofcourse@foo.invalid
wrote:

In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\". But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation. Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state. This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state. Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

What is DFA?


Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Jeroen Belleman

Does that mean a block of procedural code that is structured as a
state macnine? That\'s different from the hard-clocked logic type of
state machine that we do in an FPGA.

I explained the software state machine to a young engineer last month.
He has an ee+ce degree and never heard of it before.

 

[Don Y]

On 9/9/2022 1:05 AM, Jeroen Belleman wrote:

Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

DFA need not have *any* \"outputs\" -- whereas the whole point of Mealy and
Moore machines is *how* the outputs are derived from (state,inputs).

A DFA describes an *abstract machine*; a protocol can be represented
in a DFA; a language/grammar can be represented in a DFA; etc. It\'s
a conceptual model much like Petri Nets (yet another thing \"hardware
types\" are rarely exposed to).

To answer my own question, I\'ve two suggestions from colleagues that
I\'ll explore, to see their practical consequences. As I said, DFA
illustrations quickly get cluttered; adding MORE content increases
that clutter (and *trivial* machines are hardly worth the effort to
illustrate)

 

[Ricky]

On Friday, September 9, 2022 at 12:26:09 PM UTC-4, Don Y wrote:

On 9/9/2022 1:05 AM, Jeroen Belleman wrote:
Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.
Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

DFA need not have *any* \"outputs\" -- whereas the whole point of Mealy and
Moore machines is *how* the outputs are derived from (state,inputs).

That\'s pretty much BS. I think you mean the states can be the only output. If the DFA has no outputs, it is what they term degenerate, I believe. Every machine with no outputs is equivalent as there is no way to tell them apart.

A DFA describes an *abstract machine*; a protocol can be represented
in a DFA; a language/grammar can be represented in a DFA; etc. It\'s
a conceptual model much like Petri Nets (yet another thing \"hardware
types\" are rarely exposed to).

I recall using something like that in programming the EMSP, a military signal processor.

To answer my own question, I\'ve two suggestions from colleagues that
I\'ll explore, to see their practical consequences. As I said, DFA
illustrations quickly get cluttered; adding MORE content increases
that clutter (and *trivial* machines are hardly worth the effort to
illustrate)

I wonder what he is doing that he needs DFA rather than FSM? I expect we will never know.

The comments about a power_off state sound a lot like a FSM.

Often there are two types of documentation for a complex FSM. One is to define what the intended functionality is (using any shortcut notation that is useful). The other is a formal FSM description using a directed graph with appropriate labels for the type of FSM, (Mealy vs. Moore or a hybrid).

--

Rick C.

- Get 1,000 miles of free Supercharging
- Tesla referral code - https://ts.la/richard11209

 

[John Larkin]

On Fri, 9 Sep 2022 09:25:40 -0700, Don Y <blockedofcourse@foo.invalid>
wrote:

On 9/9/2022 1:05 AM, Jeroen Belleman wrote:
Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

The only problem with the lamentable lack of abstraction is that such
state machines most always work, usually first try. There are reasons
why.

DFA need not have *any* \"outputs\" -- whereas the whole point of Mealy and
Moore machines is *how* the outputs are derived from (state,inputs).

That\'s one way to write bug-free code, have no outputs. But it could
still crash.

A DFA describes an *abstract machine*; a protocol can be represented
in a DFA; a language/grammar can be represented in a DFA; etc. It\'s
a conceptual model much like Petri Nets (yet another thing \"hardware
types\" are rarely exposed to).

True. We are too busy building useful things that work and sell.

 

[Jeroen Belleman]

On 2022-09-09 18:25, Don Y wrote:

On 9/9/2022 1:05 AM, Jeroen Belleman wrote:
Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

Well, yes, the concept is the same, the implementation is
different. I\'ve met \"software types\" who were never exposed to
the concept. Scandalous, if you want my opinion.

Jeroen Belleman

 

[Don Y]

On 9/9/2022 11:07 AM, Jeroen Belleman wrote:

On 2022-09-09 18:25, Don Y wrote:
On 9/9/2022 1:05 AM, Jeroen Belleman wrote:
Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

Well, yes, the concept is the same, the implementation is
different. I\'ve met \"software types\" who were never exposed to
the concept. Scandalous, if you want my opinion.

Likely \"programmers\". A good software engineering curriculum covers
all of these issues as it is the basis for language design (which
drives compiler design), algorithm abstractions, etc.

A hardware engineer likely never *formally* thinks of concurrency and,
thus, never thinks of *modeling* it (via a Petri Net) -- design a processor
and suddenly knowing what you can and can\'t do concurrently is of SUPREME
importance! (how do you formalize what can/can\'t happen concurrently in
your typical HARDWARE design? Just hope it\'s \"obvious\"?)

How would you design circuits without *schematics*? Those little
squiggles on that sheet of paper don\'t *do* anything, don\'t consume
or create energy, don\'t \"do work\", etc. They are pure abstractions.
One need NEVER reify a design and yet the schematic still exists -- even
if the \"devices\" on the schematic are purely hypothetical in nature
(a diode with a 45 million PRV capable of handling 3gigaamps can still
be inserted into a schematic and the resulting circuit debated -- despite
it never being realizable!)

There is a subtle difference between Mealy/Moore \"FSMs\" (technically,
*transducers*) and DFA\'s.

A DFA consists of
a *finite* set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
a set of accept states (\"destinations\")

A Moore machine consistings of
a finite set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
* a finite set of outputs (the \"output alphabet\")
* an output function mapping each state to the output alphabet

A Mealy machine replaces the last item with
* an output function mapping each (state,inputs) to the output alphabet

A DFA is a purely abstract machine. It\'s a pure mathematical concept;
not reified in any way. Just like a schematic is nothing more than
an abstract expression of a circuit.

 

[Don Y]

On 9/9/2022 11:28 AM, Don Y wrote:

There is a subtle difference between Mealy/Moore \"FSMs\" (technically,
*transducers*) and DFA\'s.

<https://en.wikipedia.org/wiki/Finite-state_transducer>

Note the \"output tape\" (in contrast to the \"input tape\" that contains
the sequence of input symbols)

A DFA only produces a \"go/no-go\" result -- the machine \"ran to completion\"
(which means attained any one of its terminal states) or not.

 

[John Larkin]

On Fri, 9 Sep 2022 11:28:34 -0700, Don Y <blockedofcourse@foo.invalid>
wrote:

On 9/9/2022 11:07 AM, Jeroen Belleman wrote:
On 2022-09-09 18:25, Don Y wrote:
On 9/9/2022 1:05 AM, Jeroen Belleman wrote:
Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

Well, yes, the concept is the same, the implementation is
different. I\'ve met \"software types\" who were never exposed to
the concept. Scandalous, if you want my opinion.

Likely \"programmers\". A good software engineering curriculum covers
all of these issues as it is the basis for language design (which
drives compiler design), algorithm abstractions, etc.

A hardware engineer likely never *formally* thinks of concurrency and,
thus, never thinks of *modeling* it (via a Petri Net) -- design a processor
and suddenly knowing what you can and can\'t do concurrently is of SUPREME
importance! (how do you formalize what can/can\'t happen concurrently in
your typical HARDWARE design? Just hope it\'s \"obvious\"?)

How would you design circuits without *schematics*? Those little
squiggles on that sheet of paper don\'t *do* anything, don\'t consume
or create energy, don\'t \"do work\", etc. They are pure abstractions.

Every part on a schematic has a part number and a data sheet, has pins
and a package, gets purchased, gets soldered to a PCB, works. Every
squiggle becomes a trace or a plane on an etched PC board. None of
that is abstract.

One need NEVER reify a design and yet the schematic still exists -- even
if the \"devices\" on the schematic are purely hypothetical in nature
(a diode with a 45 million PRV capable of handling 3gigaamps can still
be inserted into a schematic and the resulting circuit debated -- despite
it never being realizable!)

We call out real parts on schematics. We have no 45 million volt
diodes in our library.

There is a subtle difference between Mealy/Moore \"FSMs\" (technically,
*transducers*) and DFA\'s.

A DFA consists of
a *finite* set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
a set of accept states (\"destinations\")

A Moore machine consistings of
a finite set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
* a finite set of outputs (the \"output alphabet\")
* an output function mapping each state to the output alphabet

A Mealy machine replaces the last item with
* an output function mapping each (state,inputs) to the output alphabet

A DFA is a purely abstract machine. It\'s a pure mathematical concept;
not reified in any way. Just like a schematic is nothing more than
an abstract expression of a circuit.

What\'s the difference between *finite* and finite?

Why code a DFA if it has no output and no function?

 

[a a]

On Friday, 9 September 2022 at 21:45:14 UTC+2, John Larkin wrote:

On Fri, 9 Sep 2022 11:28:34 -0700, Don Y <blocked...@foo.invalid
wrote:
On 9/9/2022 11:07 AM, Jeroen Belleman wrote:
On 2022-09-09 18:25, Don Y wrote:
On 9/9/2022 1:05 AM, Jeroen Belleman wrote:
Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

Well, yes, the concept is the same, the implementation is
different. I\'ve met \"software types\" who were never exposed to
the concept. Scandalous, if you want my opinion.

Likely \"programmers\". A good software engineering curriculum covers
all of these issues as it is the basis for language design (which
drives compiler design), algorithm abstractions, etc.

A hardware engineer likely never *formally* thinks of concurrency and,
thus, never thinks of *modeling* it (via a Petri Net) -- design a processor
and suddenly knowing what you can and can\'t do concurrently is of SUPREME
importance! (how do you formalize what can/can\'t happen concurrently in
your typical HARDWARE design? Just hope it\'s \"obvious\"?)

How would you design circuits without *schematics*? Those little
squiggles on that sheet of paper don\'t *do* anything, don\'t consume
or create energy, don\'t \"do work\", etc. They are pure abstractions.
Every part on a schematic has a part number and a data sheet, has pins
and a package, gets purchased, gets soldered to a PCB, works. Every
squiggle becomes a trace or a plane on an etched PC board. None of
that is abstract.
One need NEVER reify a design and yet the schematic still exists -- even
if the \"devices\" on the schematic are purely hypothetical in nature
(a diode with a 45 million PRV capable of handling 3gigaamps can still
be inserted into a schematic and the resulting circuit debated -- despite
it never being realizable!)
We call out real parts on schematics. We have no 45 million volt
diodes in our library.

There is a subtle difference between Mealy/Moore \"FSMs\" (technically,
*transducers*) and DFA\'s.

A DFA consists of
a *finite* set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
a set of accept states (\"destinations\")

A Moore machine consistings of
a finite set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
* a finite set of outputs (the \"output alphabet\")
* an output function mapping each state to the output alphabet

A Mealy machine replaces the last item with
* an output function mapping each (state,inputs) to the output alphabet

A DFA is a purely abstract machine. It\'s a pure mathematical concept;
not reified in any way. Just like a schematic is nothing more than
an abstract expression of a circuit.
What\'s the difference between *finite* and finite?

Why code a DFA if it has no output and no function?

forget FSA
forget DFA
AI is based on heuristics

 

[John Larkin]

On Fri, 9 Sep 2022 13:10:11 -0700 (PDT), a a <manta103g@gmail.com>
wrote:

On Friday, 9 September 2022 at 21:45:14 UTC+2, John Larkin wrote:
On Fri, 9 Sep 2022 11:28:34 -0700, Don Y <blocked...@foo.invalid
wrote:
On 9/9/2022 11:07 AM, Jeroen Belleman wrote:
On 2022-09-09 18:25, Don Y wrote:
On 9/9/2022 1:05 AM, Jeroen Belleman wrote:
Deterministic Finite Automaton. A state machine, in our lingo. I think
Don is off again on one of his overly detailed things.

Most \"hardware types\" have never been exposed to automata theory.
Say \"State Machine\" (or FINITE State Machine, to be precise) and
they think \"Mealy/Moore\". And, how many (the minimum number of)
FFs will be needed to represent the current state. And, how to
minimize with implication tables. It\'s barely an \"abstract\" notion!

Well, yes, the concept is the same, the implementation is
different. I\'ve met \"software types\" who were never exposed to
the concept. Scandalous, if you want my opinion.

Likely \"programmers\". A good software engineering curriculum covers
all of these issues as it is the basis for language design (which
drives compiler design), algorithm abstractions, etc.

A hardware engineer likely never *formally* thinks of concurrency and,
thus, never thinks of *modeling* it (via a Petri Net) -- design a processor
and suddenly knowing what you can and can\'t do concurrently is of SUPREME
importance! (how do you formalize what can/can\'t happen concurrently in
your typical HARDWARE design? Just hope it\'s \"obvious\"?)

How would you design circuits without *schematics*? Those little
squiggles on that sheet of paper don\'t *do* anything, don\'t consume
or create energy, don\'t \"do work\", etc. They are pure abstractions.
Every part on a schematic has a part number and a data sheet, has pins
and a package, gets purchased, gets soldered to a PCB, works. Every
squiggle becomes a trace or a plane on an etched PC board. None of
that is abstract.
One need NEVER reify a design and yet the schematic still exists -- even
if the \"devices\" on the schematic are purely hypothetical in nature
(a diode with a 45 million PRV capable of handling 3gigaamps can still
be inserted into a schematic and the resulting circuit debated -- despite
it never being realizable!)
We call out real parts on schematics. We have no 45 million volt
diodes in our library.

There is a subtle difference between Mealy/Moore \"FSMs\" (technically,
*transducers*) and DFA\'s.

A DFA consists of
a *finite* set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
a set of accept states (\"destinations\")

A Moore machine consistings of
a finite set of states
a finite set of input symbols (the \"alphabet\")
a transition function mapping (state,input) to next_state
a start state
* a finite set of outputs (the \"output alphabet\")
* an output function mapping each state to the output alphabet

A Mealy machine replaces the last item with
* an output function mapping each (state,inputs) to the output alphabet

A DFA is a purely abstract machine. It\'s a pure mathematical concept;
not reified in any way. Just like a schematic is nothing more than
an abstract expression of a circuit.
What\'s the difference between *finite* and finite?

Why code a DFA if it has no output and no function?
forget FSA
forget DFA
AI is based on heuristics

Electronic design is based on physics and predictable absolutes.

What ever happened to fuzzy logic? That was a hoot.

 

[Jeroen Belleman]

On 2022-09-09 22:36, John Larkin wrote:
[...]

What ever happened to fuzzy logic? That was a hoot.

The same that happened to signature analysis. Remember
that one?

Jeroen Belleman

 

[John Larkin]

On Fri, 09 Sep 2022 23:35:02 +0200, Jeroen Belleman
<jeroen@nospam.please> wrote:

On 2022-09-09 22:36, John Larkin wrote:
[...]

What ever happened to fuzzy logic? That was a hoot.


The same that happened to signature analysis. Remember
that one?

Jeroen Belleman

Yes, pseudorandom logic signals and probes to see if the waveform was
as expected. HP I think. Silly idea.

There have been a zillion computer language fads too. PL1, Pascal,
APL, Forth, C#, C++, Python.

 

[Clifford Heath]

On 9/9/22 09:10, Don Y wrote:

In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\".  But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation.  Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state.  This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state.  Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

Don,

https://github.com/katef/libfsm probably does what you want.

It is a library that takes various descriptions of state machines
(regular expressions, etc) and manipulates them in various ways,
including constructing DFAs.

It also emits Graphvis \"dot\" files that support visualisation.
You would just need to augment the output with your annotations to get
them on your vis.

JL: These automata are one of the most studied and most interesting
things in foundational computer science. Rather than calling the whole
field into question, you should try to educate yourself.

Clifford Heath

 

[John Larkin]

On Sat, 10 Sep 2022 09:33:55 +1000, Clifford Heath
<no_spam@please.net> wrote:

On 9/9/22 09:10, Don Y wrote:
In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\".  But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation.  Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state.  This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state.  Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

Don,

https://github.com/katef/libfsm probably does what you want.

It is a library that takes various descriptions of state machines
(regular expressions, etc) and manipulates them in various ways,
including constructing DFAs.

It also emits Graphvis \"dot\" files that support visualisation.
You would just need to augment the output with your annotations to get
them on your vis.

Does it generate code?

JL: These automata are one of the most studied and most interesting
things in foundational computer science. Rather than calling the whole
field into question, you should try to educate yourself.

Clifford Heath

Seems awfully academic.

We had the dean of the CS dept of a big university as a house guest. I
made the mistake of asking her what sort of programming they taught
these days. \"We don\'t teach programming!\" Boom. Faux pas big time.

CS seems to have nothing to do with programming, maybe nothing to do
with computers.

I read a popular sociology textbook just for fun, and it was. Maybe I
should get a used CS text next.

I have met a lot of ce interns and grads who don\'t know about software
state machines. Seems to me a fundamental way to code realtime,
bug-free stuff... usually better than using the resources of an RTOS.

Dijkstra said that he \"had no regular access to a computer.\"

 

[John Larkin]

On Fri, 09 Sep 2022 17:06:32 -0700, John Larkin
<jlarkin@highland_atwork_technology.com> wrote:

On Sat, 10 Sep 2022 09:33:55 +1000, Clifford Heath
no_spam@please.net> wrote:

On 9/9/22 09:10, Don Y wrote:
In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\".  But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation.  Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state.  This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state.  Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

Don,

https://github.com/katef/libfsm probably does what you want.

It is a library that takes various descriptions of state machines
(regular expressions, etc) and manipulates them in various ways,
including constructing DFAs.

It also emits Graphvis \"dot\" files that support visualisation.
You would just need to augment the output with your annotations to get
them on your vis.

Does it generate code?


JL: These automata are one of the most studied and most interesting
things in foundational computer science. Rather than calling the whole
field into question, you should try to educate yourself.

Clifford Heath

Seems awfully academic.

We had the dean of the CS dept of a big university as a house guest. I
made the mistake of asking her what sort of programming they taught
these days. \"We don\'t teach programming!\" Boom. Faux pas big time.

CS seems to have nothing to do with programming, maybe nothing to do
with computers.

I read a popular sociology textbook just for fun, and it was. Maybe I
should get a used CS text next.

I have met a lot of ce interns and grads who don\'t know about software
state machines. Seems to me a fundamental way to code realtime,
bug-free stuff... usually better than using the resources of an RTOS.

Dijkstra said that he \"had no regular access to a computer.\"

Computer science is no more about computers than astronomy is about
telescopes.

—Edsger Dijkstra

 

[Don Y]

On 9/9/2022 4:33 PM, Clifford Heath wrote:

On 9/9/22 09:10, Don Y wrote:
In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\". But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation. Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state. This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state. Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

Don,

https://github.com/katef/libfsm probably does what you want.

A cursory glance suggests not -- but, I will take a more detailed
look. Thanks.

It is a library that takes various descriptions of state machines (regular
expressions, etc) and manipulates them in various ways, including constructing
DFAs.

I have my own \"home-brewed\" compiler for an ASL that I created back
in the early 80\'s for such uses. The back-end is highly configurable
so I can adapt the code to a particular run-time implementation
(favor time or space, etc.)

> It also emits Graphvis \"dot\" files that support visualisation.

I\'m not hopeful that any algorithm could avoid making a mess
out of anything but trivial (or highly regular) automata. I
groan each time I look at a machine-generated ERD! <frown>
And those are pretty trivial, in most cases!

I don\'t mind the manual effort of drawing the diagrams as
I can add value by chosing judicious placement of various states.

You would just need to augment the output with your annotations to get them on
your vis.

*THAT* is the essence of my question, here. Where to *add*
annotation for \"on entry\" and \"on exit\" actions for each state.

Draw a simple state diagram -- 8-10 states. Add transitions
to show a high degree of interconnectedness. Annotate each
transition with some notion of the associated inputs. And,
add an *action* to each. E.g., diagram a simple grammar
(desk calculator?)

A *simple* diagram quickly gets cluttered!

Now, for each state, examine all of the transitions that terminate
at that state. Enumerate the set of actions defined by them
(presumably, they aren\'t all the same!). Assume I want to
do something in ALL of these actions to ensure the targeted
state is \"set up\" properly (e.g., \"clear accumulator\").

There is no easy way of doing this AND making it obvious to
a person examining the state diagram that this \"necessary
condition\" is in place AS that state is entered. Regardless
of HOW it is entered!

If, instead, you could factor those common actions out of
the individual transition actions and lump them into an
OnEntry() action that you declare for that (each) state,
then this ensures you don\'t forget to add those actions to
\"transition X from state Y\". And, draws attention to them
as a preset for state Z.

Ditto for every transition exiting that state -- so you
don\'t have to remember to include them in every action
associated with those transitions (and also highlighting
those activities to the reader)

Where do you put those declarations (in the *diagram*)
and what form should they take to make them obvious to
the reader -- without eating up lots of space (which
limits the complexity/size of the automaton that you
can illustrate!)

One way to handle the OnEntry mechanism is to add a \"preset\"
state upstream of each destination state. All transitions
intended for STATE are, instead, routed to this PRESTATE.
(you must exercise discipline or force compiler to impose it)
PRESTATE then has a single \"always\" transition that connects
it to STATE and invokes the OnEntry actions required on
that transition.

But, now you\'ve double the number of states to illustrate.

And, how do you address the OnExit issue? (use a PDA?)

You can put the action (function) *in* the state circle with some sort
of identification (\"In/Entry\", \"Out/Exit\") -- but that means the state
circles get larger to accommodate. (Hint: there\'s more space OUTSIDE
than IN! But, the \"outside\" is cluttered with transition vectors!)

Consider that most automata aren\'t the trivial sorts of examples
you see in the literature and its easy to see how a diagram can
quickly become unmanageable.

Returning to your suggestion (libfsm), I didn\'t see anything that
indicated support for this sort of \"annotation\". Or, even suggestions
of where it *might* put it. But, I\'ll have a look at it, tonight.

JL: These automata are one of the most studied and most interesting things in
foundational computer science. Rather than calling the whole field into
question, you should try to educate yourself.

Dunning-Kruger

 

[Clifford Heath]

On 10/9/22 15:44, Don Y wrote:

On 9/9/2022 4:33 PM, Clifford Heath wrote:
On 9/9/22 09:10, Don Y wrote:
In practical terms, one augments each transition with an
\"action\" associated with the input(s) being acted upon.

In my software implementations, I employ several hacks
to increase efficiency and range of expression possible
in a given machine. (not worth explaining, here)

In an example I\'m presently working, it would really be nice
to annotate the graphic representations of the machines with
some of these \"hacks\".  But, they aren\'t consistent with
traditional DFA illustration practices (nor are the explicit
action annotations!) so I\'m at a loss as to an *intuitive*
means of annotation.  Something that an observer unfamiliar
with the mechanism could easily infer without needing a legend!

Chief among these, I impose (optional) \"on entry\" and \"on exit\"
actions for each state.  This is a shorthand to avoid having to add
those actions to every transition entering -- or exiting -- the
state.

So, every transition entering the \"OFF\" state need not explicitly
\"remove_power()\" if an \"on entry\" action declared that action for
the OFF state.  Otherwise, any transition arriving at OFF failing
to do so could result in the machine being in the OFF state without
having already *removed* power.

Likewise, every transition leaving the OFF state (presumably for some
\"non-OFF\" state) can be assured to \"apply_power()\" by the specification
of that as an \"on exit\" action for the OFF state.

DFA illustrations quickly become cluttered (esp if inputs are named
symbolically) so any mechanism has to be relatively \"tight\"...

Don,

https://github.com/katef/libfsm probably does what you want.

A cursory glance suggests not -- but, I will take a more detailed
look.  Thanks.

It is a library that takes various descriptions of state machines
(regular expressions, etc) and manipulates them in various ways,
including constructing DFAs.

I have my own \"home-brewed\" compiler for an ASL that I created back
in the early 80\'s for such uses.  The back-end is highly configurable
so I can adapt the code to a particular run-time implementation
(favor time or space, etc.)

It also emits Graphvis \"dot\" files that support visualisation.

I\'m not hopeful that any algorithm could avoid making a mess
out of anything but trivial (or highly regular) automata.  I
groan each time I look at a machine-generated ERD!  <frown
And those are pretty trivial, in most cases!

I don\'t mind the manual effort of drawing the diagrams as
I can add value by chosing judicious placement of various states.

You would just need to augment the output with your annotations to get
them on your vis.

*THAT* is the essence of my question, here.  Where to *add*
annotation for \"on entry\" and \"on exit\" actions for each state.

Draw a simple state diagram -- 8-10 states.  Add transitions
to show a high degree of interconnectedness.  Annotate each
transition with some notion of the associated inputs.  And,
add an *action* to each.  E.g., diagram a simple grammar
(desk calculator?)

A *simple* diagram quickly gets cluttered!

Now, for each state, examine all of the transitions that terminate
at that state.  Enumerate the set of actions defined by them
(presumably, they aren\'t all the same!).  Assume I want to
do something in ALL of these actions to ensure the targeted
state is \"set up\" properly (e.g., \"clear accumulator\").

There is no easy way of doing this AND making it obvious to
a person examining the state diagram that this \"necessary
condition\" is in place AS that state is entered.  Regardless
of HOW it is entered!

If, instead, you could factor those common actions out of
the individual transition actions and lump them into an
OnEntry() action that you declare for that (each) state,
then this ensures you don\'t forget to add those actions to
\"transition X from state Y\".  And, draws attention to them
as a preset for state Z.

Ditto for every transition exiting that state -- so you
don\'t have to remember to include them in every action
associated with those transitions (and also highlighting
those activities to the reader)

Where do you put those declarations (in the *diagram*)
and what form should they take to make them obvious to
the reader -- without eating up lots of space (which
limits the complexity/size of the automaton that you
can illustrate!)

One way to handle the OnEntry mechanism is to add a \"preset\"
state upstream of each destination state.  All transitions
intended for STATE are, instead, routed to this PRESTATE.
(you must exercise discipline or force compiler to impose it)
PRESTATE then has a single \"always\" transition that connects
it to STATE and invokes the OnEntry actions required on
that transition.

But, now you\'ve double the number of states to illustrate.

And, how do you address the OnExit issue?  (use a PDA?)

You can put the action (function) *in* the state circle with some sort
of identification (\"In/Entry\", \"Out/Exit\") -- but that means the state
circles get larger to accommodate.  (Hint:  there\'s more space OUTSIDE
than IN!  But, the \"outside\" is cluttered with transition vectors!)

Consider that most automata aren\'t the trivial sorts of examples
you see in the literature and its easy to see how a diagram can
quickly become unmanageable.

Returning to your suggestion (libfsm), I didn\'t see anything that
indicated support for this sort of \"annotation\".  Or, even suggestions
of where it *might* put it.  But, I\'ll have a look at it, tonight.

Jeez Don, if you want to know how to use Graphvis, you should just read
the flaming documentation, not write an epistle here. It\'s not perfect,
but it\'s worth at least looking at before you start complaining about it.