On the finite automaton output function with the random input by the frequency of a word in the output sequence

Download article in PDF format

Authors: Melnikov S. Yu.

Annotation: The article deals with the problem of finding the output function of finite automaton with the random input by the relevant frequency of a certain word in its output sequence. The problem reduces to the discrete minimization of the linear form module. When binary shift register is regarded as finite automaton and character characteristic of the output sequence, the problem reduces to the integer-valued minimization of the linear form module under the linear constraints. The dimension of the problem is equal to the span of the register plus one, i.e. is on logarithmic dependence on the quantity of states.

Keywords: finite automaton, finding the output function, discrete minimization, shift register