Moore machine duality

Applied Mathematics
Event time: 
Monday, November 21, 2022 - 3:00pm
AKW 200
Jacques Peyrière
Speaker affiliation: 
Université Paris-Saclay
Event description: 

Let $q\ge2$ be an integer. A Moore machine $\mathscr M$ is the data of
two finite sets $A$ (the set of states) and $B$ (the output alphabet),
of an element $\mathsf i\in A$, of a mapping $h$ from
$\{1,2,\dots,q\}$ to $B$, and a mapping from $A\times\{1,2,\dots,q\}$
to $A$. The last mapping can be viewed as follows: for each $a\in A$
there are $q$ arrows labeled $1, 2,\dots, q$ stemming from $a$ and
pointing to some state. Then each word $w$ on the
alphabet $\{1,2,\dots,q\}$ defines a path starting from the initial
state $\mathsf i$ and ending at some state $i\cdot w$. So, feeding the
machine $\mathscr M$ with $w$ gives the output
$h({\mathsf i}\cdot w)$. It is known that, given a machine, there
exists a unique minimal equivalent machine (i.e., with the least
number of states). We give a new algorithm to construct minimal
machines. This algorithm also provides a proof of the existence and
uniqueness of mimimal machine.