In [1], the problem of recognizing the output function of a Moore automaton by the output sequence symbol statistics when the input is a sequence of independent identically distributed random variables was considered. Such a problem is a special case of the general problem of recognition of machines with random input and arises in a number of theoretical and applied problems. We list some of them. The problem of choosing the minimum set of multigrams in the output sequence, the probabilities of which characterize the automaton, leads to the problem of analyzing the algebraic properties of the probability distributions family of such multigrams as functions of the probability distribution at the input [2,3].

In [4], a review of papers on a similar problem is given: the probabilities of multigrams of some stationary discrete random process are known, and it is required to determine whether this process is a function on a Markov chain. In [5], for a non-autonomous shift register with a random input, an estimate was obtained of the output n-grams size, the set of probabilities of which determines the equivalence class of such an automaton, and estimates of the number of equivalence classes.

We can represent any probabilistic automaton [6,7] in the form of a sequential connection of a "source of probability" that randomly and independently generates the symbols of an 100-107 alphabet with given probabilities and a deterministic finite automaton. In a number of works (see the review [8]), the problem of synthesizing such a "source of probability" was considered, in particular, developing criteria to determine whether the desired value is generated by a combination of Bernoulli random variables with probabilities from a given set.

The search for new calculation methods leads to the problem of analyzing a class of functions that describe the probabilities of multigrams in the output sequence as functions of real variables [9].

A large number of works are devoted to the problem of discrete devices testing by applying random sequences (tests) to them and analyzing the statistics at the outputs [10,11], etc.). The problem of determining the malfunction of a device in such a formulation is the task of recognizing automata [12]. This direction is called random or pseudorandom testing. As noted in [13], the relevance of this direction is associated with the high volume of computations necessary to construct deterministic tests for complex discrete devices. A special place is taken by probabilistic compact testing methods, in which malfunctions are detected by comparing some statistical characteristics of the tested and reference device. Such a characteristic may be the frequency of occurrence in the output sequence of a fixed segment of the output symbols. The ability to change the analyzed segment and the parameters of the random sequence generator at the input of the device is a powerful tool in the hands of the researcher. In [Hamlet, 2006], situations are described where the use of deterministic tests is impractical and random tests should be used. The questions of estimating the length of random tests and the probability of detection of malfunctions are considered in [14] and [15]. We note the possibility of using probabilistic testing to detect covert channels in the analyzed equipment [16,17].

In [18] and [19], the problem of diagnosing a discrete device with random input under conditions when the output sequence of the device is known with distortions is considered.

In [20], a binary shift register with a random Bernoulli input is considered, the output function of which is known up to a certain transformation. The output sequence of the register is specified, and the input sequence is known in the variants. A statistical criterion is built to verify that the output sequence could be obtained by this input variant. The criterion is based on counting the frequencies of certain bigrams in the output sequence.

The problem considered in [1] can be formulated as follows. What information about the output function of the automaton whose input is a sequence of independent random variables can we obtain if the parameters of the "input" distribution and the relative frequency of occurrence of the symbol in the output sequence are known? How will this information change if the parameters of the "input" distribution are changed? What output functions are indistinguishable?

Similar problems can be considered in a more general form, assuming a simple or complex [21] Markov dependence in the input sequence. The main ideas of the developed approach, in principle, can be transferred from the "independent" to the "Markov" case. In fact, a sequence of random variables connected into a finite Markov chain can be considered as a sequence of states of a suitable finite automaton (the transition graph of which is the transition graph of the Markov chain under consideration) that processes a sequence of independent random variables with a properly selected distribution [22]. Let the output function of such an automaton be identical (output = state). Then the machine that processes the Markov chain can be represented as a serial connection of two machines, the input of the first of which receives a sequence of independent random variables. Thus, the problem reduces to the one considered above, only for a more complex automaton (Figure 1). The same can be done if the input sequence is a more general random process -a function on a finite Markov chain. In this case, the output function of the first automaton may not be identical. Certain difficulties in this direction are associated both with an increase in the number of states of a new combined automaton, and therefore with an increase in the dimension of computational problems, and with the requirement of strong connectivity of the serial connection of two automata, the first of which should provide all possible models of randomness in the input sequence.

For the case of a binary shift register, we will use the direct representation of probability functions as functions of the Markov chain parameters. A Markov chain with two states is determined by the transition probability matrix and the initial probability distribution, which we assume to be stationary. The transition probability matrix has a size of 2 × 2 , and due tostochasticity it is determined by two real parameters 𝜆 and 𝜉, 0 < 𝜆, 𝜉 < 1. These parameters can be interpreted as the probabilities of transitions "from state 0 to state 1" and "from state 1 tostate 0", respectively. In [23], for the case when the symbols of the input sequence are connected into a simple homogeneous stationary Markov chain, an expression is obtained for the probability of the symbol "1" in the output sequence of the register. The same work describes the equivalence relation on a set of Boolean functions that occurs when registers with these output functions have the same probability functions. Here we consider the problem of determining the equivalence class of the output function from symbol statistics, reduce it to the form of the discrete optimization problem, and compare the Bernoulli and Markov cases in terms of obtaining information for recognizing the output function and dimensions of discrete optimization problems.

Let 𝑉 𝑛 be the space of 𝑛-dimensional binary vectors, 𝐹 𝑛 be the set of Boolean functions of 𝑛 arguments, 𝑛 = 1, 2, …. For 𝑓 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ) ∈ 𝐹 𝑛 by 𝐴 𝑓 = (𝑋 = {0, 1}, 𝑉 𝑛 , 𝑌 = {0, 1}, ℎ, 𝑓) we denote the Moore automaton with set of states 𝑉 𝑛 , the transition function ℎ, determined by function in the family 𝑀 𝑛 is equal to zero. It is easy to see that Ω 𝑛 is the union of a finite number of smooth curves in a unit square. In particular, it can be shown that both diagonals of the square, {(𝜆, 𝜉 )|𝜆 + 𝜉 = 1} and {(𝜆, 𝜉 )|𝜆 = 𝜉} belong to the set Ω 𝑛 , if 𝑛 ⩾ 3. The set Ω 𝑛 has Lebesgue measure zero.

Theorem 2. For (𝜆, 𝜉 ) ∈ {(0, 1) × (0, 1)} \Ω 𝑛 , by the value of 𝑃 𝑓 (𝜆, 𝜉 ), we can unambiguously indicate the class of statistical equivalence of the function 𝑓. This equivalence class corresponds to the vector of the Markov weight structure 𝜇 0 , which is the only solution of the equation

If (𝜆, 𝜉 ) ∈ Ω 𝑛 , then this equation has more than one solution, and the vector of the Markov weight structure of 𝑓 is contained among these solutions.

Let 𝑦 (𝑖) = 𝑓 (𝑥 (𝑖) , 𝑥 (𝑖+1) , … , 𝑥 (𝑖+𝑛−1) ), 𝑖 = 1, 2, … be the output sequence of the automaton 𝐴 𝑓 in the scheme described above,

The binary sequence 𝑦 (𝑖) is stationary, therefore, the law of large numbers is valid [24]:

Theorem 3. Let (𝜆, 𝜉 ) ∈ {(0, 1) × (0, 1)} \Ω 𝑛 . The probability that the minimization problem

has a unique solution, tends to 1 with 𝑁 → ∞. This unique solution corresponds the class of statistical equivalence of output function 𝑓. For the case (𝜆, 𝜉 ) ∈ Ω 𝑛 , we can only say that the vector of the weighted Markov structure of the true output function 𝑓 is contained among the solutions of problem (7).

Comparing the results obtained for the case when the input sequence is a Markov chain with the results obtained for the case of a Bernoulli sequence, the following can be noted.

1. Probabilistic functions in both cases are determined by the weights (sums of values) of the Boolean function of the outputs on special subsets of space 𝑉 𝑛 . These subsets consist of vectors that have the same probability in a particular model (in the independent case, vectors of the same weight, in Markov, vectors with the same frequency of occurrence of bigrams). In the first case, the probability function is a polynomial in the parameter 𝑝 of the Bernoulli scheme; in the second, it is a fractional rational function in the parameters 𝜆 and 𝜉, that determine the Markov chain. 2. The relations of statistical equivalence on 𝐹 𝑛 are introduced on the basis of the identity of probability functions; from the statistical equivalence of two Boolean functions with a Markov input dependence follows their statistical equivalence with a Bernoulli input. The equivalence of two functions is equivalent to the equality of their weights on the mentioned subsets 𝑉 𝑛 . In the independent case the number of such subsets is 𝑛 + 1, in the Markov case the number of such subsets is 3 4 𝑛 2 𝑂(𝑛). The number of equivalence classes for the Bernoulli case is equal to exp ( 𝑛 2 2 + 𝑂(𝑛 ln 𝑛)), for the Markov case is equal to exp ( 5𝑛 3 4 ln 𝑛 + 𝑂(𝑛 3 )). 3. In the set of all kinds of distributions (the parameter 𝑝 of the Bernoulli distribution belongs to the interval (0, 1), the parameters (𝜆, 𝜉 ) of the transition matrix of the Markov chain belong to the square (0, 1)×(0, 1)), a subset Ω of the "special" distributions is distinguished. For all distributions not from the set Ω, the value of the probability function allows us to uniquely indicate the equivalence class of the output function. If the distribution belongs Ω, then there are at least two nonequivalent output functions for which the probability values of "1" in the output sequence coincide. The Lebesgue measure of the set Ω of "special distributions" in the distribution space is zero: in the first case it turns out to be a finite set of points of the segment, in the second -the set of points of a finite number of smooth curves inside a square. Thus, analyzing the problem of recognizing an unknown function of outputs by symbol statistics, we can say that the proposed approach, while complicating the probabilistic nature of the input sequence (switching from the Bernoulli scheme to the Markov chain), leads, on the one hand, to the possibility of obtaining more detailed information about the recognizable function; on the other hand, the dimension of discrete optimization problems increases.