An Approximate Method for Calculating the Distance Between Regular Languages for Multitape Finite Automata - Grigoryan, Tigran A. (Изд-во НАН РА)
Sets of word tuples, accepted by multitape finite automata and a metric space for languages accepted by these automata, are considered. These languages are represented using the same notation as the known notation of regular expressions for languages accepted by one-tape automata. The only difference is the interpretation of the ”concatenation” operation in the notation. An algorithm is proposed for calculating the introduced distance between regular languages accepted by multitape finite automata. Դիտարկվում են բազմաժապավեն վերջավոր ավտոմատների կողմից ճանաչվող բառերի կորտեժների բազմություններ և այդ ավտոմատների կողմից ճանաչվող լեզուների վրա սահմանված մետրիկական տարածություն: Այս լեզուները ներկայացված են նույն գրելաձևով, ինչ մեկ ժապավենանոց ավտոմատների կողմից ճանաչվող կանոնավոր լեզուների համար կանոնավոր արտահայտությունները: Միակ տարբերությունը <կոնկատենացիա> գործողության մեկնաբանությունն է: Առաջարկվում է ալգորիթմ, որով հաշվվում է բազմաժապավեն վերջավոր ավտոմատների կողմից ճանաչվող կանոնավոր արտահայտությունների միջև հեռավորությունը` ըստ ներմուծված մետրիկայի: Рассматриваются регулярные выражения для многоленточных конечных автоматов. Каждое регулярное выражение описывает язык - множество кортежей слов, принимаемых данным многоленточным конечным автоматом. Также рассмотрено метрическое пространство языков, принимаемых многоленточными конечными автоматами. Эти языки представлены с помощью той же нотации, которая используется в регулярных выражениях для языков, распознаваемых одноленточными автоматами. Единственная разница - в иной интерпретации каждой операции ”конкатенация” нотации. Определена метрика и предложен алгоритм для вычисления расстояния между регулярными выражениями, принимаемыми многоленточными конечными автоматами.
Keywords: Mathematical cybernetics; Computer science