A colleague asked me for a copy of this, earlier today. After
thrashing around in my archive -- to no avail -- I figured it
was easier just to redevelop it. <frown>

<https://mega.nz/file/wq5WVJpK#reZk1lqt21E-4S1PyTr5wKE9RmRMD8mn3RV4diAVAZg>

[Posting it inline would make a complete mess of the formatting.
And, I am unsure as to how ES would respond to my UUencoding it?]

It's origins are in a tool I wrote to reverse engineer hardware DFAs
(used as "keys" for software package licensing tools). But, due
to the way it solves that problem, it can also be used to exhaustively
*test* such DFA -- as well as *software* DFA implementations. It does
this by selectively applying stimuli to the DFA and monitoring changes
in its state. Then, using this information to build a graph of the DFA.

It does not rely on having direct control over the current state
and, in fact, can be started regardless of the current state of
the DFA. It's sole ability is to selectively apply stimuli to
cause the DFA to reveal its actions by means of observed new state.
As such, it has to coax the DFA into a particular state in order
to exercise various stimuli which have yet to be applied and
characterized *in* that state.

The designer can compare this deduced graph to the intended graph,
AS DESIGNED, to verify that all -- and only the intended -- edges
are present with no omissions or additions. For complex DFAs,
this is probably the only practical approach to exhaustive testing
(imagine having to push every POSSIBLE sequence of buttons on
a product to verify proper operation!)

It exploits the evolving detail of the graph to find better ways to
get to incompletely explored states using an SPP-inspired algorithm.
E.g., if there is a path from state A to state B through states 1,
2, 3 and 4 using a sequence of successively applied stimuli -- but,
a *better* path is discovered though state Q (fewer hops), it will
update the map to reflect this "shortcut" and exploit it whenever
it has need to move to state B from state A. If an even BETTER
path is discovered, then this shortcut will be replaced by the
improved shortcut! This cuts the running time of the algorithm by
reducing the number of stimuli that must be applied (number of times
the DFA must be "clocked").

Starting, as it does, with no knowledge of the graph means it is more accurately classified as a CTP implementation and, thus, more complex.

Sadly, it ONLY handles DFAs so is of little practical use in software implementations as they more typically use the far more versatile PDA.
[This was the caveat that I've pointed out to my colleague but he
was curious, nonetheless.]

And, the DFA must not have any terminal nodes or cycles. (A stimulus
that effectively "resets" the DFA can address that requirement.)

Untested as I don't have a compiler on this machine. But, it *should*
work (it's a relatively trivial algorithm; SPP is "CS101" material and
there should be enough notes here to sort out what the code SHOULD do!)

You can build a simple, table-driven DFA and verify that this
algorithm reveals the equivalent table (the algorithm is fast, even
for large DFAs).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)