Содержание к диссертации
Введение
1 Предварительные сведения 16
2 Дескриптивная слолсность окрестности регулярного языка в метрике Хэмминга 24
2.1 Окрестность языка в метрике Хэмминга 24
2.2 Верхние оценки недетерминированной и детерминированной сложности 27
2.3 Нижняя оценка недетерминированной сложности . 31
2.4 Нижняя оценка детерминированной сложности 33
2.5 Сопоставление оценок детерминированной сложности и результатов экспериментов 47
3 Дескриптивная слолсность применения конечного трансдьюсера 54
3.1 Конечные трансдьюсеры 54
3.2 Недетерминированная сложность применения конечного трансдыосера 58
3.3 Детерминированная сложность применения конечного трансдьюсера 62
4 Дескриптивная слолсность динамической окрестности регулярного языка 64
4.1 Динамическая окрестность языка 64
4.2 Регулярность динамической окрестности регулярного языка 66
4.3 Верхняя оценка недетерминированной сложности . 69
Список литературы 72
- Окрестность языка в метрике Хэмминга
- Нижняя оценка детерминированной сложности
- Детерминированная сложность применения конечного трансдьюсера
- Регулярность динамической окрестности регулярного языка
Введение к работе
Актуальность темы. Хорошо известна та важная роль, которую играет в теоретических и практических разделах современной информатики понятие регулярного языка. В различных ситуациях оказывается удобным использовать разные способы задания регулярных языков — детерминированные и недетерминированные конечные автоматы, право-и лево линейные грамматики, регулярные выражения и др. Для каждого из этих способов уместен вопрос о максимально экономичном задании регулярного языка. Именно такие вопросы ставятся и решаются в рамках теории дескриптивной сложности формальных языков. В ней с каждым способом задания языка связывается некоторая числовая мера и исследуется минимально возможное значение этой меры для данного языка. Применительно к регулярным языкам классическими мерами дескриптивной сложности являются детерминированная и недетерминированная сложность.
Детерминированная сложность регулярного языка определяется количеством состояний минимального детерминированного конечного автомата, распознающего рассматриваемый язык. Для регулярного языка L будем обозначать его детерминированную сложность через sc(L).
Задача о максимально эффективном представлении языка детерминированным автоматом является крайне естественной. О важности подобных исследований говорит еще и тот факт, что детерминированная сложность дает нижнюю оценку для временной сложности и сложности относительно количества памяти вычислений, связанных с регулярным языком, представленным при помощи детерминированного конечного автомата. Вопросы эффективного представления языка при помощи детерминированных автоматов поднимаются в ранних работах, касающихся регулярных языков (в частности, в [14, 16]). Первыми отечественными исследованиями в данной области являются работы А. Н. Маслова. В [4] доказана точность известных верхних оценок детерминированной сложности объединения, пересечения и итерации языков, а также получена верхняя оценка детерминированной сложности циклической перестановки букв слов языка. В [5] операция циклической перестановки рассмотрена более подробно и получены аналогичные результаты для контекстно-свободных языков. Размер автомата именно как мера дескриптивной сложности языка впервые рассматривался в [10].
Как известно, класс регулярных языков замкнут относительно многих естественных операций. Это позволяет изучать не только дескриптивную сложность самих языков, но и дескриптивную сложность операций над ними, используя единую меру сложности. Если операция сохраняет регулярность языка, то уместен вопрос о том, какое изменение происходит в сложности языка при применении к нему этой операции.
Таблица 1: Детерминированная сложность некоторых операций
Более формально, пусть имеется операция f(L), которая сохраняет регулярность языка. Тогда детерминированной сложностью операции / является функция
sc(/) : N ->> N,
которая каждому натуральному числу п ставит в соответствие наибольшее значение детерминированной сложности, которой может обладать язык f(L) при условии, что язык L имеет сложность п:
sc(/)(n) = max sc(/(L)).
sc(L)=n
Аналогичным образом определяется детерминированная сложность операции, аргументами которой являются не один, а несколько языков. В этом случае областью определения функции sc(/) является пространство Nfc, где к — количество аргументов операции /.
Современный вид теория дескриптивной сложности регулярных языков приняла в начале 90-х годов сначала в работах Ж.-К. Бирже [7, 8], а затем и в исследованиях Шень Ю и К. Саломаа [22]. С этого момента можно говорить о взрывном росте интереса к детерминированной сложности регулярных языков: появляется значительное количество новых статей по этой теме, а спустя некоторое время организуется серия ежегодных конференций Descriptive Complexity of Formal Systems, посвященных изучению этих вопросов. Хорошим обзором современного состояния дел в этой области является работа [21].
В таблице 1 представлена детерминированная сложность некоторых основных операций над регулярными языками на основе работы [22]. В этой таблице подразумевается, что языки L\ и Ь2 имеют сложность п и т соответственно. Через R обозначается реверсаль языка (разворот всех слов языка в обратном порядке), через С — дополнение языка, через * — итерация языка.
Недетерминированная сложность регулярного языка определяется минимальным количеством состояний, на которых можно построить
Таблица 2: Недетерминированная сложность некоторых операций
недетерминированный конечный автомат, распознающий рассматриваемый язык. Важно отметить, что для регулярного языка может не существовать одного минимального недетерминированного автомата — автоматов с минимальным количеством состояний может быть несколько, и они могут быть друг с другом не изоморфны. Однако само минимальное количество состояний, тем не менее, всегда определяется однозначно. Для регулярного языка L его недетерминированную сложность будем обозначать через nsc(L). Недетерминированная сложность операции над регулярными языками определяется аналогично детерминированной сложности операции.
Несмотря на то, что в начале 1990-х гг. Бирже исследовал как детерминированную, так и недетерминированную сложность операций над регулярными языками, дальнейшее изучение недетерминированной сложности другими исследователями было широко продолжено только в начале 2000-х гг. Результаты этих исследований приведены в таблице 2 (в ней приняты те же соглашения, что и в таблице 1). Обзор основных результатов по недетерминированной сложности регулярных языков дан в работе [17].
Одной из ключевых особенностей регулярных языков (весьма существенной с практической точки зрения) является крайняя простота вычислительных моделей (прежде всего, конечных автоматов), при помощи которых осуществляются те или иные действия над регулярными языками. Так, например, один из самых простых в реализации и при этом крайне эффективный алгоритм Ахо-Карасика (см. [1]) поиска образца в тексте основан на использовании конечных автоматов. Суть этого классического алгоритма заключается в том, что по заданному образцу строится конечный автомат, который распознает множество всех слов, содержащих данный образец в качестве подстроки. Далее на вход этого автомата подается текст, в котором требуется осуществить поиск. Такой алгоритм работает за линейное от длины текста время и за линейную от длины образца память.
Распространенным обобщением задачи поиска образца является по-
иск одного из образцов из словаря или, в общем случае, поиск по регулярному выражению. Такая задача тоже хорошо решается при помощи конечных автоматов: по регулярному выражению строится конечный автомат, на вход которого подается текст для поиска.
Следующей задачей, пришедшей из практики, является задача приближенного поиска образца. Имеющийся образец или текст, в котором требуется осуществить поиск, содержит ошибки, вызванные опечатками, ошибками распознавания, помехами, мутациями или иными причинами. Эта задача также находит эффективное решение при помощи конечных автоматов: строится автомат, который вместе с образцом ищет также другие похожие варианты (с заданным количеством ошибок). Классическими работами в этой области являются [18, 20].
Естественным соединением двух предыдущих задач является задача приближенного поиска по регулярному выражению. Один из подходов к решению этой задачи состоит в следующем. Если рассмотреть операцию, которая по множеству слов возвращает множество близких к ним слов относительно некоторого расстояния, то окажется, что для практически всех естественных расстояний эта операция сохраняет регулярность. Другими словами, окрестность регулярного языка (регулярного выражения) относительно некоторого расстояния будет регулярным языком. Более того, такое преобразование языка в его окрестность во многих случаях достаточно хорошо формализуется. Это позволяет в явном виде выписать конечный автомат, распознающий нужную окрестность исходного регулярного выражения. Далее приближенный поиск регулярного выражения ведется уже на основе построенного конечного автомата. Хороший обзор существующих алгоритмов приближенного поиска дан в [6, 13].
Для различных практический приложений крайне важен вопрос о том, насколько большим окажется автомат, с помощью которого будет осуществляться приближенный поиск по регулярному выражению. Такая постановка вопроса приводит нас к необходимости исследования дескриптивной сложности окрестности языка в некоторой метрике (мы, как и многие исследователи, будем рассматривать случай классической метрики Хэмминга; окрестность радиуса г языка L в метрике Хэммин-га будем обозначать через 0(L,r)). В [18] кроме собственно алгоритма построения автомата приводится оценка количества состояний в этом автомате. Однако данный вопрос рассматривается лишь для случая регулярного языка, состоящего из одного слова. В результате можно сформулировать следующую задачу
Задача 1. Оценить дескриптивную сложность окрестности регулярного языка в метрике Хэмминга.
До этого момента речь шла о дескриптивной сложности конкретных
операций над регулярными языками. Представляется вполне естественным желание получить оценки дескриптивной сложности сразу для некоторого класса операций, сохраняющих регулярность языка. Например, в качестве такого класса можно рассматривать операции, задаваемые конечными трансдьюсерами.
Конечный трансдьюсер (абстрактный конечный автомат в терминах книги [2]) является модификацией недетерминированного конечного автомата, в которой каждый переход помечен не одним, а двумя словами (возможно, над разными — входным и выходным — алфавитами). На вход трансдьюсера подается некоторое слово. По мере чтения этого слова в автомате трансдьюсера (используя первые слова в каждом переходе) будем последовательно записывать вторые слова соответствующих переходов. В результате на выходе получится некоторое слово над выходным алфавитом, которое будем называть образом исходного входного слова при применении данного трансдьюсера. При помощи конечных трансдьюсеров можно преобразовывать слова, а значит, и целые языки — объединяя образы всех слов языка. Результат применения трансдьюсера г к языку L будем обозначать через t(L), а количество состояний в трансдьюсере будем обозначать через \т\.
Важное значение для теории конечных трансдьюсеров имеет теорема о том, что образ регулярного языка при применении к нему конечного трансдьюсера остается регулярным языком ([15], теорема 1.6). В нашем случае это позволяет сформулировать следующую задачу:
Задача 2. Оценить дескриптивную сложность применения к регулярному языку конечного трансдьюсера.
Классические алгоритмы приближенного поиска, основанные на рассмотрении окрестности языка в некоторой метрике с фиксированным числом ошибок, не во всех приложениях дают желаемый результат. В [9] предлагается алгоритм (также на основе конечных автоматов) для поиска образца в тексте, который содержит не более чем заданное количество ошибок в каждом блоке заданной длины — окрестность слова или языка, устроенную таким образом, будем называть динамической окрестностью. Если L — некоторый язык, г — максимально допустимое количество ошибок, а — длина блока, то соответствующую динамическую окрестность будем обозначать через (D(L,r,). Подобная постановка задачи представляется очень естественной: чем более длинный образец или текст мы обрабатываем, тем большее количество ошибок там может содержаться. Пожалуй, такая постановка задачи актуальней всего для имеющей большое практическое значение проблемы поиска образца в цепочке ДНК. Если имеется некоторый образец ДНК и нужно проверить его вхождение в какую-то цепочку ДНК, то мы должны учитывать,
что в цепочке вполне могли произойти какие-то мутации или погрешности экспериментов, в результате чего отдельные нуклеотиды могли быть изменены. Такие изменения не могут быть очень концентрированными (в противном случае цепочка ДНК разрушится), они должны быть более или менее равномерно распределены по всей длине цепочки. Поиск достаточно длинного образца в такой цепочке необходимо производить с учетом приведенных особенностей. Более подробную информацию об особенностях поиска в цепочках ДНК можно найти в [12, 19].
Естественное желание обобщить поиск одного образца до поиска по регулярному выражению приводит к следующей задаче:
Задача 3. Оценить дескриптивную сложность динамической окрестности регулярного языка.
Целью работы является получение оценок детерминированной и недетерминированной сложности для операций взятия окрестности языка в метрике Хэмминга, применения к языку конечного трансдьюсера и взятия динамической окрестности языка.
Научная новизна. Все результаты диссертации являются новыми.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории дескриптивной сложности регулярных языков, а также при разработке алгоритмов приближенного поиска.
Апробация результатов работы. Результаты диссертации докладывались на Международной алгебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шев-рина (Екатеринбург, 2005), Международной конференции по теории языков и автоматов и ее приложениям (Таррагона, 2007), научных семинарах «Алгебраические системы» и «Компьютерные науки» кафедры алгебры и дискретной математики Уральского государственного университета имени А. М. Горького (Екатеринбург, 2007-2009), Российско-индийском семинаре «Алгебра, комбинаторика, сложность» (Екатеринбург, 2009), семинаре кафедры математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М. В. Ломоносова (Москва, 2009).
Публикации. Основные результаты диссертации опубликованы в работах [23]-[27]. Работы [23] и [27] опубликованы в изданиях, входящих в перечень ВАК.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации составляет 78 страниц, библиография содержит 64 наименования.
Окрестность языка в метрике Хэмминга
Напомним, что через Е мы обозначаем множество всех слов над алфавитом . Расстоянием на множестве Е будем называть всякую функцию р : S х Е -» MU {со}, определяемую следующим образом. Расстояние р(х, у) между словами хиу — это минимальная стоимость последовательности операций, преобразующей х ву (и оо, если такой последовательности не существует). Стоимость последовательности операций равна сумме стоимостей отдельных элементарных операций. Итак, для того, чтобы определить какое-то конкретное расстояние, необходимо задать элементарные операции и их стоимость. Для обозначения элементарной операции, позволяющей переходить при фиксированных словах х и у надЕ от любого слова w — uxv, для и, v Є S , к слову w = uyv, будем использовать запись 5(х,у). Для обозначения того факта, что данная операция имеет стоимость с О, будем использовать запись 5(х,у) = с. Таким образом, определить какое-то конкретное расстояние можно при помощи задания некоторого (обычно конечного) набора выражений вида 5(х, у) = с, где х ж у — это различные слова над Е, ас- некоторое неотрицательное число. Нетрудно заметить, что при таком определении вне зависимости от выбора конкретного набора элементарных операций и их стоимостей выполняются неравенства р(х, х) = 0, р{х, у) 0 и р(ж, z) р(х,у) + p{y,z) для любых ж, у и z. Если стоимость каждой элементарной операции положительна и для каждой операции 5(х,у) = t существует элементарная операция 5(у, х) = t, то такое расстояние называют симметричным. Если расстояние симметричное, то множество всех слов относительно этого расстояния образует метрическое пространство. Симметричное расстояние будем называть метрикой.
В большинстве приложений используются следующие операции: вставка ((А, а) для некоторой буквы а), удаление (5(а, Л) для некоторой буквы а), замена (5(а, Ь) для некоторых букв о и 6, а ф 6), перестановка (5(ab, Ъа) для некоторых букв а и Ь, а ф Ь). Для данного числа г молено определить г-окрестность слова и относительно расстояния р — множество всех слов, расстояние от которых до слова w не превосходит г. Такую окрестность будем обозначать через Op(w,r) или, когда расстояние зафиксировано, просто О{уо,г). Окрестность одного слова естественным образом обобщается до окрестности языка: Расстояние р на Е называется аддитивным если для каждого г 0 и В работе [12] доказано, что аддитивная окрестность языка сохраняет регулярность: Предложение 2.1. Если р аддитивное расстояние, L регулярный язык и г 0, то Op{L,r) также регулярный язык. Расстояние Хэмминга между двумя словами одинаковой длины определяется количеством позиций, в которых эти слова различаются. Более формально, расстояние Хэмминга р(х, у) задается следующим набором элементарных операций: Расстояние Хэмминга между словами aabba и ababa равно 2, т.к. они различаются только во 2-ой и 3-ей позициях. Нетрудно вычислить, например, единичную окрестность в метрике Хэмминга слова aabba (над алфавитом {а, &}). Это окрестность состоит из ело aabba, babba, abbba, aaaba, aabaa и aabab. Другим популярным расстоянием, имеющим большое практическое применение, является расстояние Левенштейна (см. [3]). Расстояние Левенштейна между двумя словами определяется минимальным количеством необходимых вставок, удалений и замен символов, преобразующих одно слово в другое. Формально расстояние Левенштейна задается следующим набором элементарных операций: Расстояние Левенштейна между словами abaa и bbaab равно 2, т.к. для того, чтобы получить второе слово, необходимо в первом слове заменить первую букву на b и вставить букву b в конце слова. Единичная окрестность в метрике
Левенштейна слова abaa (над алфавитом {а, 6}) состоит из слов abaa, bbaa, аааа, abba, abab, baa, ааа, aba, aabaa, babaa, abbaa, abaaa, ababa и abaab. И расстояние Хэмминга, и расстояние Левенштейна являются аддитивными ([12]). В данной диссертации мы будем рассматривать расстояние Хэмминга. Расстояние Левенштейна будет использоваться в ряде случаев для демонстрации возможности переноса результатов на другие виды расстояний. 2.2 Верхние оценки недетерминированной и детерминированной сложности Поскольку расстояние Хэмминга является аддитивным, то по утверждению 2.1 окрестность регулярного языка в метрике Хэмминга остается регулярным языком. Это значит, что можно изучать дескриптивную сложность окрестности в метрике Хэмминга в терминах недетерминированной и детерминированной сложностей. Для того, чтобы получить верхние оценки этих сложностей, в явном виде сконструируем автомат, распознающий окрестность языка в метрике Хэмминга, на основе автомата исходного языка. Далее будут рассматриваться автоматы, множества состояний которых являются начальными участками числового ряда N = {0,1,... } Для т, тт, Є N и m п будем обозначать множество {т, т +1,..., п — 1} через [т, п). Для числа п и числового множества F через п + F будем обозначать множество Umep{n + гп}. Лемма 2.1. Если язык LCE распознается недетерминированным автоматом с п состояниями, то г-окрестность этого языка в метрике Хэмминга может быть распознана при помощи недетерминированного автомата с n(r + 1) состояниями. Доказательство. Пусть язык L распознается недетерминированным автоматом A = ([0,n),, 5, s, F). Рассмотрим недетерминированный автомат А — ([0, n(r + 1)), Е, 5 , s, \Jri=0{n + F)), где функция переходов 6 определена следующим образом (здесь 0 g n, 0 fc г, а Є Е): 5 {q + nk, a) = (nk + 5(q, a)) U (n(k + 1) + (J 6(q,a j),
Нижняя оценка детерминированной сложности
В работе [18] доказано, что размер минимального детерминированного автомата для г-окрестности слова ат равен (7І1) В соответствии с леммой 1.4 детерминированная сложность языка {аш} равна га+ 2. Обозначая sc(am) через п, получаем, что При фиксированном г это дает полиномиальную нижнюю оценку детерминированной сложности окрестности регулярного языка. Однако напомним, что верхняя оценка, полученная в предложении 2.3, имеет экспоненциальный характер. Далее для каждого п 4 мы построим язык, детерминированная сложность которого равна п, а его 1-окрестность имеет детерминированную сложность п-2п—2п 4+п. Эта величина вместе с полученной ранее верхней оценкой п 2n + 1 принадлежат одному классу сложности Q(n2n). Далее через Е будем обозначать алфавит {а, 6}. Для каждого п 4 определим детерминированный автомат Нп = ([0,n), Е, Jn,0, {0}) следующим образом: Автомат Нп изображен на рисунке 9. Нетрудно заметить, что автомат Нп является минимальным автоматом своего языка. Следовательно, детерминированная сложность этого языка равна п. Интересно отметить, что граф, лежащий в основании автомата Нп, является важным экстремальным примером для теории неотрицательных матриц [53] и теории синхронизируемых автоматов [8]. Нам не известно является ли это случайным совпадением или существует какая-то скрытая взаимосвязь между экстремальными свойствами автомата Нп в различных областях. Через HNn обозначим автомат, полученный из Нп так, как это описано в лемме 2.1: В соответствии с леммой 2.1 автомат HNn распознает 1-окрестность 0(L(Hn), і). Через HDn обозначим детерминированный автомат, полученный из HNn при помощи стандартной конструкции автомата подмножеств: Зафиксируем параметр п и будем в дальнейшем использовать 6 вместо 6 п, А вместо Ап и Р вместо Fn. Множество Р С [0, 2п) будем называть (нетривиально) достижи мым, если отметить, что граф, лежащий в основании автомата Нп, является важным экстремальным примером для теории неотрицательных матриц [53] и теории синхронизируемых автоматов [8]. Нам не известно является ли это случайным совпадением или существует какая-то скрытая взаимосвязь между экстремальными свойствами автомата Нп в различных областях. Через HNn обозначим автомат, полученный из Нп так, как это описано в лемме 2.1: В соответствии с леммой 2.1 автомат HNn распознает 1-окрестность 0(L(Hn), і). Через HDn обозначим детерминированный автомат, полученный из HNn при помощи стандартной конструкции автомата подмножеств: Зафиксируем параметр п и будем в дальнейшем использовать 6 вместо 6 п, А вместо Ап и Р вместо Fn. Множество Р С [0, 2п) будем называть (нетривиально) достижи мым, если существует (непустое) слово w , такое что Р = А(0, и ). Нашей первой целью будет описание достижимых подмножеств автомата HDn. Следующие две леммы очевидны и справедливы не только для автомата HDn (см. доказательство предложения 2.3). Лемма 2.3.
Каждое достижимое мноэюество автомата HDn содержит в точности один элемент из [0,п). Лемма 2.4. Каждое нетривиально достижимое множество автомата HDn вместе с некоторым элементном р Є [0,п) также содержит элемент р + п. Для q Є [0,n), qi Є [n, 2n), 1 г s, будем обозначать через семейство всех подмножеств Р множества {q} U [п, 2тг), таких что Р содержит элементы q, q + п и по крайней мере один из элементов д . Через будем обозначать подсемейство всех подмножеств мощности семейства (2). Так для п = 4 семейство {1,5; 4 V 7} состоит из множеств {1,4,5}, {1, 5,7}, {1, 4, 5,6}, {1, 5, 6,7} и {1,4, 5,6, 7}, а семейство {1, 5; 4 V 7}4 из множеств {1,4, 5,6} и {1, 5,6,7}. Следующие пять лемм позволяют установить некоторые зависимости между элементами достижимых множеств (лемма 2.5) и между существует (непустое) слово w , такое что Р = А(0, и ). Нашей первой целью будет описание достижимых подмножеств автомата HDn. Следующие две леммы очевидны и справедливы не только для автомата HDn (см. доказательство предложения 2.3). Лемма 2.3. Каждое достижимое мноэюество автомата HDn содержит в точности один элемент из [0,п). Лемма 2.4. Каждое нетривиально достижимое множество автомата HDn вместе с некоторым элементном р Є [0,п) также содержит элемент р + п. Для q Є [0,n), qi Є [n, 2n), 1 г s, будем обозначать через семейство всех подмножеств Р множества {q} U [п, 2тг), таких что Р содержит элементы q, q + п и по крайней мере один из элементов д . Через будем обозначать подсемейство всех подмножеств мощности семейства (2). Так для п = 4 семейство {1,5; 4 V 7} состоит из множеств {1,4,5}, {1, 5,7}, {1, 4, 5,6}, {1, 5, 6,7} и {1,4, 5,6, 7}, а семейство {1, 5; 4 V 7}4 из множеств {1,4, 5,6} и {1, 5,6,7}. Следующие пять лемм позволяют установить некоторые зависимости между элементами достижимых множеств (лемма 2.5) и между достижимостью различных семейств множеств (леммы 2.6-2.9). Лемма 2.5. Пусть w Є Е+ иР — Д(0,ги). 1. Если О Є Р, то Р Є {0, щ п + 1}. 2. .ЕСУШ Р содержит состояние q Є [1, n — 1) и \w\ q, то
Детерминированная сложность применения конечного трансдьюсера
Чтобы получить оценку детерминированной сложности применения конечного трансдьюсера к регулярному языку, воспользуемся полученной оценкой недетерминированной сложности и стандартной конструкцией автомата подмножеств для детерминизации недетерминированного автомата. Следствие 3.1. Пусть L — регулярный язык, г — нормализованный конечный трансдьюсер. Тогда Доказательство. Пусть L — регулярный язык, г — нормализован ный конечный трансдьюсер. В соответствии с леммой 3.2 язык T(L) можно распознать при помощи НКА, имеющего не более nsc(L)r SC(L)T СОСТОЯНИЙ. Используя стандартную конструкцию подмножеств преобразуем полученный недетерминированный автомат в детерми нированный, который будет иметь не более 2SC(L) ITI состояний. Экспоненциальный рост детерминированной сложности языка при применении конечного трансдьюсера может быть объяснен недетерминированностью, заложенной в самом трансдьюсере. Как отмечалось во введении, существуют примеры серий недетерминированных автоматов с п состояниями, множество слов которых распознается детерминированными автоматами не менее чем с 2п состояниями. Поэтому процесс детерминизации языка т(Ь) может существенно уве личить количество состояний, необходимых для распознавания этого языка при помощи детерминированного конечного автомата. Приведенная экспоненциальная оценка, полученная из общих соображений, не является слишком завышенной. В разделе 2.4 для каждого п 4 строится регулярный язык, детерминированная сложность которого равна п, при этом 1-окрестности этого языка в метрике Хэмминга имеет детерминированную сложность п 2П — 2П 4 + п. Как мы знаем (см. пример 3.1) 1-окрестность в метрике Хэмминга можно представить в виде конечного нормализованного трансдьюсера с двумя состояниями. Из этого можно сделать вывод о верности порядка приведенной верхней оценки (по крайней мере для трансдьюсеров с двумя состояниями).
Окрестность языка определяет множество слов, близких к словам этого языка с точки зрения выбранного расстояния. Часто на практике речь идет о некотором эталонном слове (или языке) и о множестве слов, полученных из эталонного при помощи фиксированного количества допустимых искажений или ошибок. Однако такой «статический» подход к определению множества близких слов не подходит для моделей, где вероятность появления ошибок в слове является не фиксированной величиной, а зависит от длины этого слова. Например, в процессе передачи сигнала тем большее количество искажений может произойти, чем более длинное слово мы передаем. Это заставляет нас прийти к понятию динамической окрестности слова. Для расстояния Хэмминга, слова w и чисел г и будем называть динамической окрестностью слова w (или г--окрестностью слова w) множество слов 0(w,r,), каждый участок длины которых отличается от соответствующего участка слова w не более чем в г позициях. Более формально, динамическая окрестность слова w определяется следующим образом: Способ обобщения окрестности слова до окрестности языка остается прежним: Рассмотрим более подробно процесс сравнения двух слов с точки зрения динамической окрестности. Пусть даны слова w и v одинаковой длины и нужно проверить, принадлежит ли слово v динамической г--окрестности слова w. Процесс проверки удобно представлять себе следующим образом. Выписываем слова w и v друг под другом и накладываем поверх этих слов окно с фиксированной шириной в символов. Если в процессе движения этого окна от начала слов к концу в окне в каждый момент времени видно не более г ошибок, то слово v принадлежит г--окрестности слова w. В каждый момент времени состояние окна при сравнении слов w и v удобно характеризовать вектором ошибки е = e(w, v) — -мерным вектором, і-я компонента которого равна 1, если буквы сравниваемых слов в г -й слева позиции окна различаются, и 0 в остальных случаях. Через е будем обозначать сумму компонент вектора ошибки е, которую назовем его весом. Вектор ошибки будем называть допустимым, если его вес не превосходит г. В начальный момент времени, когда окно находится целиком слева от всех букв сравниваемых слов, вектор ошибки состоит целиком из нулей. Затем каждый раз, сдвигая окно на одну позицию вправо, мы добавляем в поле видимости по одному символу сравниваемых слов. При этом информация в векторе ошибок сдвигается справа налево, а на крайнюю правую позицию помещается результат сравнения новой пары символов. Вектор ошибок в начальный момент времени будем обозначать через е_, затем, по мере движения окна, будем увеличивать индекс вектора ошибки на 1. Как нетрудно заметить, последний вектор ошибки имеет индекс \w\ — . Процесс движения окна проиллюстрирован на рисунке 20. Два следующих утверждения, касающихся веса вектора ошибки, очевидны. Прежде чем начать изучать вопрос дескриптивной сложности динамической окрестности регулярного языка, необходимо выяснить, сохраняет ли регулярность динамическая окрестность. В работе [19] доказывается регулярность динамической окрестности одного слова. Мы же дадим ответ на этот вопрос для произвольного регулярного языка.
Для этого мы построим конечный трансдьюсер, который будет преобразовывать регулярный язык в его динамическую окрестность. Теорема 4.1. Пусть L С — регулярный язык, г, 0. Тогда 0(L, г, ) — регулярный язык. Доказательство. Пусть L — регулярный язык, г, 0. Построим конечный трансдьюсер т = (Q,Z,H,8,q0}F), который будет преобразовывать язык L с в его динамическую r-f-окрестность (D(L,r,). В качестве Q возьмем множество допустимых векторов ошибок. В качестве начального состояния q0 возьмем нулевой вектор ошибок. В качестве множества заключительных состояний выберем все множество Q. Множество переходов 5 определим следующим образом. Переход (е, а, 6, /) для е, f Є Q и а, 6 Є Е содержится в множестве 6 тогда и только тогда, когда / = (р2, ,Рг, х), где е = (рг,р2, . ,Ре) и х — 0, если а = Ь, и х = 1, если афЬ. Пример трансдьюсера г для динамической 1- -окрестности приведен на рисунке 21. Покажем, что в построенном трансдьюсере при чтении пары слов w v значение вектора ошибки этих слов в каждый момент времени соответствует текущему состоянию трансдьюсера. Более формально, нужно доказать, что если имеется последовательность переходов
Регулярность динамической окрестности регулярного языка
Способ обобщения окрестности слова до окрестности языка остается прежним: Рассмотрим более подробно процесс сравнения двух слов с точки зрения динамической окрестности. Пусть даны слова w и v одинаковой длины и нужно проверить, принадлежит ли слово v динамической г--окрестности слова w. Процесс проверки удобно представлять себе следующим образом. Выписываем слова w и v друг под другом и накладываем поверх этих слов окно с фиксированной шириной в символов. Если в процессе движения этого окна от начала слов к концу в окне в каждый момент времени видно не более г ошибок, то слово v принадлежит г--окрестности слова w. В каждый момент времени состояние окна при сравнении слов w и v удобно характеризовать вектором ошибки е = e(w, v) — -мерным вектором, і-я компонента которого равна 1, если буквы сравниваемых слов в г -й слева позиции окна различаются, и 0 в остальных случаях. Через е будем обозначать сумму компонент вектора ошибки е, которую назовем его весом. Вектор ошибки будем называть допустимым, если его вес не превосходит г. В начальный момент времени, когда окно находится целиком слева от всех букв сравниваемых слов, вектор ошибки состоит целиком из нулей. Затем каждый раз, сдвигая окно на одну позицию вправо, мы добавляем в поле видимости по одному символу сравниваемых слов. При этом информация в векторе ошибок сдвигается справа налево, а на крайнюю правую позицию помещается результат сравнения новой пары символов. Вектор ошибок в начальный момент времени будем обозначать через е_, затем, по мере движения окна, будем увеличивать индекс вектора ошибки на 1. Как нетрудно заметить, последний вектор ошибки имеет индекс \w\ — . Процесс движения окна проиллюстрирован на рисунке 20. Два следующих утверждения, касающихся веса вектора ошибки, очевидны. Прежде чем начать изучать вопрос дескриптивной сложности динамической окрестности регулярного языка, необходимо выяснить, сохраняет ли регулярность динамическая окрестность. В работе [19] доказывается регулярность динамической окрестности одного слова. Мы же дадим ответ на этот вопрос для произвольного регулярного языка. Для этого мы построим конечный трансдьюсер, который будет преобразовывать регулярный язык в его динамическую окрестность. Теорема 4.1. Пусть L С — регулярный язык, г, 0. Тогда 0(L, г, ) — регулярный язык. Доказательство. Пусть L — регулярный язык, г, 0. Построим конечный трансдьюсер который будет преобразовывать язык L с в его динамическую r-f-окрестность (D(L,r,).
В качестве Q возьмем множество допустимых векторов ошибок. В качестве начального состояния q0 возьмем нулевой вектор ошибок. В качестве множества заключительных состояний выберем все множество Q. Множество переходов 5 определим следующим образом. Переход (е, а, 6, /) для е, f Є Q и а, 6 Є Е содержится в множестве 6 тогда и только тогда, когда / = (р2, ,Рг, х), где е = (рг,р2, . ,Ре) и х — 0, если а = Ь, и х = 1, если афЬ. Пример трансдьюсера г для динамической 1- -окрестности приведен на рисунке 21. Покажем, что в построенном трансдьюсере при чтении пары слов w v значение вектора ошибки этих слов в каждый момент времени соответствует текущему состоянию трансдьюсера. Более формально, нужно доказать, что если имеется последовательность переходов Это утверждение мы будем доказывать индукцией по г. Для г = О значением вектора ошибки e-i{w,v) является нулевой вектор. Им же, по определению трансдьюсера т, является начальное состояние д0. База индукции доказана. Предположим, что доказываемое утверждение выполнено для г. Покажем, что оно справедливо и для г + 1. Пусть вектор ошибки ei-e(w,v) имеет значение (pi,... ,ре)- По предположению индукции qi = ei-i(w,v) = (pi,... ,р ). По определению перехода qi г — ?г+і состояние gi+i является вектором (р2,... ,р,ж), где а; = 0, если аг+і = &г+ь и ж = 1, если Oj+i 7 м-і- Этот вектор совпадает со значением вектора ошибки ei+i_e(w,v), т.е. еі+і_г(го,г;) = g +i-Шаг индукции доказан. Теперь докажем основное утверждение о том, что язык т{Ь) совпадает с динамической окрестностью 0(L,r,). Сначала покажем, что т(Ь) С 0(L, г, ). Возьмем слово v из языка т(Ь). Это означает, что найдется такое слово w из языка L, что (w,v) Є 7(т). Покажем, что слово г принадлежит динамической г--окрестности слова w, т.е. множеству слов {и:Н = И & Vi = 0...\v\- p(w[i+l,i+],v[i+l,i+]) Л. Поскольку все переходы в г имеют вид (е,а, Ь, /), где а, Ь Є Е, то преобразование слова с помощью г изменяет его буквы, но не меняет его длину. Поэтому \v\ — ги. Теперь покажем, что для г = 0 ... \v\ — слова v[i + 1,г + } и w[i + l,i + } различаются не более чем в г позициях. Зафиксируем г. По лемме 4.1 расстояние Хэмминга между словами v[i + 1,г 4- } и гф+1,г+] равно весу г-ro вектора ошибки ei(w,v). Далее, поскольку (w,v) Є 7(т), найдется такая последовательность qi,..., qn состояний aibi агЬ2 апЬп трансдьюсера т, что до —) gi — ... — дп, го = ai.. ,ап и г) = fri... Ьп. Как мы показали ранее, в этом случае вектор ошибки е ги, v) совпадает с состоянием qi+g. Поскольку множество всех состояний Q состоит только из допустимых векторов, имеем p(w[i + 1, г + ], v[i + 1,г + ]) = \\ei(w,v)\\ = \\qi+e\\ г. Значит, слово v принадлежит динамической r- -окрестности слова w и, следовательно, всему языку 0(L,r,). Докажем теперь, что (Э(Ь,г,) С т{Ь). Возьмем слово v из динамической окрестности 0(L, г, ).
Это значит, что найдется такое слово w из языка L, что слово v принадлежит динамической окрестности слова w. Для того, чтобы показать, что v Є T(L), достаточно доказать, что (ад, v) Є Т {т). Поскольку v Є (D(w,r,), длины слов v и w совпадают. Представим слова w и v в виде последовательностей букв а\... ап и 6i... bn соответственно. Покажем, что найдутся такие состояния qi Є Q,l г п, что в трансдьюсере г определены переходы (Й-І,ОІ,ЬІ,Ф), 1 г п. Для г = 1... п в качестве состояния qi возьмем вектор ошибки ei_c(w,v). Поскольку v Є G(w,r,), по лемме 4.2 вес вектора ошибки ei-e(w:v) не превосходит г для г = 1.. .п, т.е. эти вектора ошибок являются допустимым, а значит, принадлежат множеству состояний Q. Для і = 1... п переход (#г-і, di,bi, qi) в трансдьюсере г определен, поскольку (&_! и qi — это два последовательных вектора ошибок при чтении в словах w и v букв щ и fy соответственно. Это совпадает с определением множества переходов 5 в трансдьюсере т. Мы построили конечный трансдьюсер, который преобразует язык L в его динамическую окрестность 0(L,r,). Значит, в силу утверждения 3.1, из регулярности языка L следует регулярность языка
