Part 3. Mathematical models

On the complexity of converting pairs of words with respect to drop-in operations of a special type

P. S. Dergach^a, S. R. Amirova<sup>b

a</sup> Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
^b Lomonosov Moscow State University in Baku

Abstract: This article is devoted to finding the distance between pairs of words in a general finite alphabet under the action of the operation of replacing one letter into two (adjacent) and calculating the corresponding shortest chain of substitutions (if it exists). Initially, the problem was posed in a more general formulation for a pair of regular languages, but later the formulation of the problem was clarified. At the same time, two possibilities are considered - with the permission to replace letters that were previously absent in the original word or with the prohibition of such operations. This direction is relevant and can be used, for example, in the theory of noise-resistant coding. In particular, it is worth mentioning the Levenstein metric, which inspires similar research on a new type of letter substitution operations.

Keywords: text recognition, Levenshtein distance, metric, optimal algorithm.