Identification method for invert-ible finite state machine with known output function
This paper presents some simple adaptive identification experiments with a finite state machine (FSM) A = (X, S, Y, taken from an exclusive class of invertible strongly connected deterministic FSM specified by a nondeterministic FSM R = (X, S, Y, Ф,) with one or two transition variants. In R, a set S1 is a x/y-successor of a subset So С S if S1 = {s : 3s0 E S0 (s E & 0) = y)}. A successor graph of the FSM R is an oriented graph constructed in the following way. Each non-empty subset S0 С S is represented by a node v(S0) of the graph. A node v(S0) is an end vertex if |S0| 2. If a node v(S0) is not an end vertex, then there exists an edge labelled by x/y from this node to a node v(S1), where S1 is the x/y-successor of S0. A node v(S0) is decidable if it is an end vertex or there exists x0 such that all edges x0/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.