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 S₁ is a x/y-successor of a subset So С S if S₁ = {s : 3s₀ E S₀ (s E & <^(x, s₀) = y)}. A successor graph of the FSM R is an oriented graph constructed in the following way. Each non-empty subset S₀ С S is represented by a node v(S₀) of the graph. A node v(S₀) is an end vertex if |S₀| ^ 2. If a node v(S₀) is not an end vertex, then there exists an edge labelled by x/y from this node to a node v(S₁), where S₁ is the x/y-successor of S₀. A node v(S₀) is decidable if it is an end vertex or there exists x₀ such that all edges x₀/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

Authors

References