Случайные блуждания в бесповторных языках
Аннотация
Дюжева М.В. СЛУЧАЙНЫЕ БЛУЖДАНИЯ В БЕСПОВТОРНЫХ ЯЗЫКАХ, выпускная квалификационная работа бакалавра: стр. 37, рис. 1, табл. 2, библ.: 12 назв.
Ключевые слова: МАРКОВСКАЯ ЭНТРОПИЯ, БЕСПОВТОРНЫЙ ЯЗЫК, СЛУЧАЙНОЕ БЛУЖДАНИЕ, СЛУЧАЙНЫЙ МАРШРУТ, ПРЕФИКСНОЕ ДЕРЕВО, ЧАСТОТА ВЕТВЛЕНИЯ, РЕГУЛЯРНЫЕ ПРИБЛИЖЕНИЯ
Объект исследования – бесповторные языки. Цель работы – исследование марковской энтропии бесповторных языков.
Рассмотрены два метода оценки марковской энтропии бесповторного языка. Первый метод основан на построении случайных маршрутов в префиксном дереве языка. Энтропия оценивается через частоту ветвления – параметр случайного маршрута, матожидание которого очень близко к марковской энтропии. Представлен алгоритм построения случайного маршрута, а также реализованы алгоритмы проверки принадлежности слова заданному бесповторному языку. Второй метод представляет собой экстраполяционную оценку энтропии регулярных приближений языка. В работе представлены алгоритмы, необходимые для реализации данного метода.
На основании экспериментального исследования ряда бесповторных языков сделан вывод о том, что рассмотренные методы позволяют получить достаточно близкие оценки марковской энтропии языка.
Ключевые слова: МАРКОВСКАЯ ЭНТРОПИЯ, БЕСПОВТОРНЫЙ ЯЗЫК, СЛУЧАЙНОЕ БЛУЖДАНИЕ, СЛУЧАЙНЫЙ МАРШРУТ, ПРЕФИКСНОЕ ДЕРЕВО, ЧАСТОТА ВЕТВЛЕНИЯ, РЕГУЛЯРНЫЕ ПРИБЛИЖЕНИЯ
Объект исследования – бесповторные языки. Цель работы – исследование марковской энтропии бесповторных языков.
Рассмотрены два метода оценки марковской энтропии бесповторного языка. Первый метод основан на построении случайных маршрутов в префиксном дереве языка. Энтропия оценивается через частоту ветвления – параметр случайного маршрута, матожидание которого очень близко к марковской энтропии. Представлен алгоритм построения случайного маршрута, а также реализованы алгоритмы проверки принадлежности слова заданному бесповторному языку. Второй метод представляет собой экстраполяционную оценку энтропии регулярных приближений языка. В работе представлены алгоритмы, необходимые для реализации данного метода.
На основании экспериментального исследования ряда бесповторных языков сделан вывод о том, что рассмотренные методы позволяют получить достаточно близкие оценки марковской энтропии языка.