Applied Theory of Coding, Automata and Graphs

Identification method for invertible finite state machine with known output function

A. O. Zhukovskaja, V. N. Trenkaev

Tomsk State University, Tomsk

Abstract: This paper presents some simple adaptive identification experiments with a finite state machine (FSM) $A=(X,S,Y,\psi,\varphi)$ taken from an exclusive class of invertible strongly connected deterministic FSM specified by a nondeterministic FSM $R=(X,S,Y,\Psi,\varphi)$ with one or two transition variants. In $R$, a set $S_1$ is a $x/y$-successor of a subset $S_0\subseteq S$ if $S_1=\{s\colon\exists s_0 \in S_0\ (s\in\Psi(x, s_0)\ \&\ \varphi(x,s_0)=y)\}$. A successor graph of the FSM $R$ is an oriented graph constructed in the following way. Each non-empty subset $S_0\subseteq S$ is represented by a node $v(S_0)$ of the graph. A node $v(S_0)$ is an end vertex if $|S_0|\le2$. If a node $v(S_0)$ is not an end vertex, then there exists an edge labelled by $x/y$ from this node to a node $v(S_1)$, where $S_1$ is the $x/y$-successor of $S_0$. A node $v(S_0)$ is decidable if it is an end vertex or there exists $x_0$ such that all edges $x_0/y$ direct to decidable nodes. It is proved that if the node $v(S)$ of the successor graph of the FSM $R$ is decidable, then there exists a simple adaptive homing experiment with $A$. This fact results in the following method for identification of $A$. First, construct the successor graph of $R$ and find the decidable nodes in it. Second, if the node $v(S)$ is decidable, then carry out a simple adaptive homing experiment with $A$. At last, execute an identification experiment with $A$ when the initial state of $A$ is known. Methods for producing homing experiments and identification experiments with the initial FSM of an exclusive class are well known.

Keywords: finite state machines, successor graphs, identification experiments.

UDC: 519.713.4

DOI: 10.17223/2226308X/10/55