Event time:
Wednesday, May 1, 2024 - 1:00pm
Location:
LOM 214
Speaker:
Jacques Peyrière
Speaker affiliation:
Université Paris-Saclay
Event description:
Let q ≥ 2 be an integer. A Moore machine M is the data of
(1) two finite sets A (the set of states) and B (the output alphabet),
(2) an element i ∈ A (the initial state),
(3) a mapping h from {1, 2, … , q} to B
(4) a mapping from A×{1, 2, … , q} to A (the transition function).
The last mapping can be viewed as follows: for each a ∈ A there are q
arrows labeled 1, 2,… , q stemming from a and pointing to some state.
Then each word w on the alphabet {1, 2, … , q} defines a path starting
from the initial state i and ending at some state i · w. So, feeding the
machine M with w gives the output h(i · w).
We define the dual of a Moore machine. It appears that the bidual
of a machine M is equivalent to M and is minimal in that sense that
it has the least number of states among the equivalent machines.
This gives a new proof of the existence and uniqueness of the minimal
machine and provides an algorithm to construct it.
Special note:
Seminar talk is supported in part by the Mrs. Hepsa Ely Silliman Memorial Fund.