Polyhedra of Finite State Machines and Their Use in the Identification Problem

摘要

The possible sets of joint distribution of the word occurrence frequencies in the finite state machine input and output sequences are considered. A geometric description of such sets as convex polyhedra in a real unit cube of suitable dimension is proposed. A method has been developed for comparison of unknown and reference automata by the observed input and output sequence fragments. The method does not require installation to the fixed initial state.