ONT Re: Differential Logic A -- Discussion
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
DLOG A. Discussion Note 25
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Refreshed from that idyllic interlude,
it's back to the grinstone once again,
to the "finite state automaton" (FSA)
that Table 2 shows as M c X x Y x Z.
Table 2. Transduction Triples
o---------o---------o---------o
| X | Y | Z |
o---------o---------o---------o
| 1 | a | c |
| 1 | b | d |
| 1 | c | d |
| 1 | d | b |
o---------o---------o---------o
| 2 | a | b |
| 2 | b | a |
| 2 | c | d |
| 2 | d | c |
o---------o---------o---------o
| 3 | a | d |
| 3 | b | c |
| 3 | c | d |
| 3 | d | b |
o---------o---------o---------o
Graphical modes of visualizing FSA's can be extremely
useful when the number of states is relatively small.
Figure 3 shows one way of depicting the machine M,
as an "edge-painted node-labeled digraph". Here,
the term "painted", say, with "palette" X, means
that each edge is associated with a subset of X,
the term "labeled", say, with "label set" Y = Z,
means that there is a bijective map between the
nodes and the set Y, which is here equal to Z,
and the term "digraph" is the same thing as
saying "directed graph". When the context
is understood, it will be most convenient
to refer to such a construction as the
"graph" of the machine M, or Graph(M).
o-----------------------------------------------------------o
| |
| o---o |
| / \ |
| o o |
| | a | |
| o o |
| / \ / \ |
| / o---o \ |
| / / | \ |
| 2 / / | \ 3 |
| ^ / | v |
| / / | \ |
| / v | \ |
| / / 2 | \ |
| / / | \ |
| o---o / | o---o |
| / \ / 1 | / \ |
| o o----------->-|---------o o |
| | b | v 1 | d | |
| o o-----------<-|---------o o |
| \ / 13 | / \ / |
| o---o | / o---o |
| \ | / / |
| \ | 123 / / |
| \ | ^ / |
| \ | / / |
| ^ | / v |
| 3 \ | / / 2 |
| \ |/ / |
| \ o---o / |
| \ / \ / |
| o o |
| | c | |
| o o |
| \ / |
| o---o |
| |
o-----------------------------------------------------------o
Figure 3. FSA as Edge-Painted Node-Labeled Digraph
Looking over the graph, it should tell us the same thing
as any of our previous representations of M, for example:
T_1 = a:c + b:d + c:d + d:b
T_2 = a:b + b:a + c:d + d:c
T_3 = a:d + b:c + c:d + d:b
In so many words:
1 takes a to c, b and c to d, and d to b.
2 switches a and b, and switches c and d.
3 maps a to d and cycles through d, b, c.
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
http://www.cs.bsu.edu/homepages/mighty/history.html
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o