Resumen
In some previous publications, we investigated the properties of a special binary relation, which was sometimes called the equivalence relation at infinity. For a pair of finite languages, the equality of infinite iterations of these languages is necessary and sufficient to fulfill this relationship. Earlier, we considered examples of the application of this relation: both examples describing the necessary conditions for its implementation, and examples of its use in various fields of formal language theory. The problems considered in this paper can be called the tasks of investigating the necessary conditions for the equality of infinite iterations of finite languages, building algorithms based on these conditions to verify that a finite language belongs to a set of morphic images of extended maximal prefix codes and algorithms for constructing corresponding morphisms, as well as the use of such algorithms in some problems of the theory of formal languages. The main subject of the paper is motivation to consider such tasks. And, apparently, the main ?component? of such motivation is the plan of proving the possibility of reducing the equality P = NP to the special hypothesis of the theory of formal languages formulated earlier in one of our previous publications. It is worth noting that the first version of this plan was published by us in 2011; here is an amended version, and with a much larger number of comments. However, the basic idea is the same, but here it has already been formalized specifically, and the solutions to many auxiliary subproblems necessary for the implementation of such a plan have already been published over the past time. Briefly, this basic idea can be formulated as follows. For some nondeterministic finite automaton, a pair of finite languages is constructed in a special way, and for this pair it is shown that if the above hypothesis were fulfilled, then there would be an algorithm for checking the fulfillment of the equivalence relation at infinity in polynomial time. But, on the other hand, taking an arbitrary nondeterministic finite automaton and considering it as an NSPRI automaton defined in our previous publications, we could construct a pair of finite languages corresponding to this automaton in polynomial time; and this pair satisfies the equivalence relation at infinity if and only if the language of the NSPRI automaton coincides with the universal language over a given alphabet (i.e., a language containing all possible words). Thus, the fulfillment of the above hypothesis entails the fulfillment of the equality P = NP.