Journal or Publication Title:
Date of publication:
Volume:
ISSN:
Official URL:
Additional Information:
Գրիգորյան Տիգրան Ա., Григорян Тигран А.
Title:
Other title:
Բազմաժապավեն վերջավոր ավտոմատների համար կանոնավոր լեզուների միջև հեռավորությունը հաշվող մոտավոր եղանակ ; Приближенный метод вычисления расстояния между регулярными языками для многоленточных конечных автоматов
Creator:
Subject:
Mathematical cybernetics ; Computer science
Uncontrolled Keywords:
Multitape finite automata ; Regular languages ; Metric space
Coverage:
Abstract:
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. Դիտարկվում են բազմաժապավեն վերջավոր ավտոմատների կողմից ճանաչվող բառերի կորտեժների բազմություններ և այդ ավտոմատների կողմից ճանաչվող լեզուների վրա սահմանված մետրիկական տարածություն: Այս լեզուները ներկայացված են նույն գրելաձևով, ինչ մեկ ժապավենանոց ավտոմատների կողմից ճանաչվող կանոնավոր լեզուների համար կանոնավոր արտահայտությունները: Միակ տարբերությունը <կոնկատենացիա> գործողության մեկնաբանությունն է: Առաջարկվում է ալգորիթմ, որով հաշվվում է բազմաժապավեն վերջավոր ավտոմատների կողմից ճանաչվող կանոնավոր արտահայտությունների միջև հեռավորությունը` ըստ ներմուծված մետրիկայի: Рассматриваются регулярные выражения для многоленточных конечных автоматов. Каждое регулярное выражение описывает язык - множество кортежей слов, принимаемых данным многоленточным конечным автоматом. Также рассмотрено метрическое пространство языков, принимаемых многоленточными конечными автоматами. Эти языки представлены с помощью той же нотации, которая используется в регулярных выражениях для языков, распознаваемых одноленточными автоматами. Единственная разница - в иной интерпретации каждой операции ”конкатенация” нотации. Определена метрика и предложен алгоритм для вычисления расстояния между регулярными выражениями, принимаемыми многоленточными конечными автоматами.