Дескриптивная сложность некоторых преобразований регулярных языков тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



, 01...........

Российская академия наук I 0034Э4525

Уральское отделение Институт математики и механики

На правах рукописи

Поваров Григорий Андреевич

Дескриптивная сложность

некоторых преобразований регулярных языков

01.01.09 — дискретная математика и математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург — 2010

2 5 НДС 901^

Работа выполнена на кафедре алгебры и дискретной математики ГОУ ВПО Уральский государственный университет им. А. М. Горького

Научный руководитель: доктор физико-математических наук,

профессор М. В. Волков

Официальные оппоненты: доктор физико-математических наук,

профессор В. А. Молчанов, кандидат физико-математических наук, старший научный сотрудник С. А. Афонин

Ведущая организация: Уральский государственный технический

университет — У ПИ имени Б. Н. Ельцина

Защита диссертации состоится «14» апреля 2010 г. в «14» часов на заседании диссертационного совета Д 004.006.04 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан до .» марта 2010 г.

Ученый секретарь диссертационного совета, кандидат физико-математических старший научный сотрудник

Общая характеристика работы

Актуальность темы. Хорошо известна та важная роль, которую играет в теоретических и практических разделах современной информатики понятие регулярного языка. В различных ситуациях оказывается удобным использовать разные способы задания регулярных языков — детерминированные и недетерминированные конечные автоматы, право-и леволинейные грамматики, регулярные выражения и др. Для каждого из этих способов уместен вопрос о максимально экономичном задании регулярного языка. Именно такие вопросы ставятся и решаются в рамках теории дескриптивной сложности формальных языков. В ней с каждым способом задания языка связывается некоторая числовая мера и исследуется минимально возможное значение этой меры для данного языка. Применительно к регулярным языкам классическими мерами дескриптивной сложности являются детерминированная и недетерминированная сложность.

Детерминированная сложность регулярного языка определяется количеством состояний минимального детерминированного конечного автомата, распознающего рассматриваемый язык. Для регулярного языка Ь будем обозначать его детерминированную сложность через &с{Ь).

Задача о максимально эффективном представлении языка детерминированным автоматом является крайне естественной. О важности подобных исследований говорит еще и тот факт, что детерминированная сложность дает нижнюю оценку для временной сложности и сложности относительно количества памяти вычислений, связанных с регулярным

ЯЗЫКОМ, ПреДСТаВЛеННЫм При ПОМОЩИ ДеХврмИНИрОЬаККОГО КОНЕЧНОГО автомата. Вопросы эффективного представления языка при помощи детерминированных автоматов поднимаются в ранних работах, касающихся регулярных языков (в частности, в [14, 16]). Первыми отечественными исследованиями в данной области являются работы А. Н. Маслова. В [4] доказана точность известных верхних оценок детерминированной сложности объединения, пересечения и итерации языков, а также получена верхняя оценка детерминированной сложности циклической перестановки букв слов языка. В [5] операция циклической перестановки рассмотрена более подробно и получены аналогичные результаты для контекстно-свободных языков. Размер автомата именно как мера дескриптивной сложности языка впервые рассматривался в [10].

Как известно, класс регулярных языков замкнут относительно многих естественных операций. Это позволяет изучать не только дескриптивную сложность самих языков, но и дескриптивную сложность операций над ними, используя единую меру сложности. Если операция сохраняет регулярность языка, то уместен вопрос о том, какое изменение происходит в сложности языка при применении к нему этой операции.

операция sc

Li U ¿2 mn

¿lDl/2 mn

Cih) n

R(Li) 2"

Li • ¿2 (2m — 1)2" 1

3 ■ 2n~2

Таблица 1: Детерминированная сложность некоторых операций

Более формально, пусть имеется операция f(L), которая сохраняет регулярность языка. Тогда детерминированной сложностью операции / является функция

sc(/): N N,

которая каждому натуральному числу п ставит в соответствие наибольшее значение детерминированной сложности, которой может обладать язык f(L) при условии, что язык L имеет сложность п:

sc(/)(n) = max sc(/(L)).

sc(L)=n

Аналогичным образом определяется детерминированная сложность операции, аргументами которой являются не один, а несколько языков. В этом случае областью определения функции sc(/) является пространство

Mfc „_„ и —„ „„.,„„„„„„ „„„г,....... (

A4 J IV nvjitl 1V/OIUVJ cbfSl J iVlOll 1UU UHV/J^Uii^ttU J •

Современный вид теория дескриптивной сложности регулярных языков приняла в начале 90-х годов сначала в работах Ж.-К. Бирже [7, 8], а затем и в исследованиях Шень Ю и К. Саломаа [22]. С этого момента можно говорить о взрывном росте интереса к детерминированной сложности регулярных языков: появляется значительное количество новых статей по этой теме, а спустя некоторое время организуется серия ежегодных конференций Descriptive Complexity of Formal Systems, посвященных изучению этих вопросов. Хорошим обзором современного состояния дел в этой области является работа [21].

В таблице 1 представлена детерминированная сложность некоторых основных операций над регулярными языками на основе работы [22]. В этой таблице подразумевается, что языки Li и L^ имеют сложность п и т соответственно. Через R обозначается реверсаль языка (разворот всех слов языка в обратном порядке), через С — дополнение языка, через * — итерация языка.

Недетерминированная сложность регулярного языка определяется минимальным количеством состояний, на которых можно построить

операция пес

Ь\ и тп + п+1

МП 1/2 тп

0(1,) 0(2"~1)

ад 71+ 1

Ь\ • ¿2 т + п

ц п + 1

Таблица 2: Недетерминированная сложность некоторых операций

недетерминированный конечный автомат, распознающий рассматриваемый язык. Важно отметить, что для регулярного языка может не существовать одного минимального недетерминированного автомата — автоматов с минимальным количеством состояний может быть несколько, и они могут быть друг с другом не изоморфны. Однако само минимальное количество состояний, тем не менее, всегда определяется однозначно. Для регулярного языка Ь его недетерминированную сложность будем обозначать через шс(¿). Недетерминированная сложность операции над регулярными языками определяется аналогично детерминированной сложности операции.

Несмотря на то, что в начале 1990-х гг. Бирже исследовал как детерминированную, так и недетерминированную сложность операций над регулярными языками, дальнейшее изучение недетерминированной сложности другими исследователями было широко продолжено только в начале 2000-х гг. Результаты этих исследований приведены в таблице 2 (в ней приняты те же соглашения, что и в таблице 1). Обзор основных результатов по недетерминированной сложности регулярных языков дан в работе [17].

Одной из ключевых особенностей регулярных языков (весьма существенной с практической точки зрения) является крайняя простота вычислительных моделей (прежде всего, конечных автоматов), при помощи которых осуществляются те или иные действия над регулярными языками. Так, например, один из самых простых в реализации и при этом крайне эффективный алгоритм Ахо-Карасика (см. [1]) поиска образца в тексте основан на использовании конечных автоматов. Суть этого классического алгоритма заключается в том, что по заданному образцу строится конечный автомат, который распознает множество всех слов, содержащих данный образец в качестве подстроки. Далее на вход этого автомата подается текст, в котором требуется осуществить поиск. Такой алгоритм работает за линейное от длины текста время и за линейную от длины образца память.

Распространенным обобщением задачи поиска образца является по-

иск одного из образцов из словаря или, в общем случае, поиск по регулярному выражению. Такая задача тоже хорошо решается при помощи конечных автоматов: по регулярному выражению строится конечный автомат, на вход которого подается текст для поиска.

Следующей задачей, пришедшей из практики, является задача приближенного поиска образца. Имеющийся образец или текст, в котором требуется осуществить поиск, содержит ошибки, вызванные опечатками, ошибками распознавания, помехами, мутациями или инымн причинами. Эта задача также находит эффективное решение при помощи конечных автоматов: строится автомат, который вместе с образцом ищет также другие похожие варианты (с заданным количеством ошибок). Классическими работами в этой области являются [18, 20].

Естественным соединением двух предыдущих задач является задача приближенного поиска по регулярному выражению. Один из подходов к решению этой задачи состоит в следующем. Если рассмотреть операцию, которая по множеству слов возвращает множество близких к ним слов относительно некоторого расстояния, то окажется, что для практически всех естественных расстояний эта операция сохраняет регулярность. Другими словами, окрестность регулярного языка (регулярного выражения) относительно некоторого расстояния будет регулярным языком. Более того, такое преобразование языка в его окрестность во многих случаях достаточно хорошо формализуется. Это позволяет в явном виде выписать конечный автомат, распознающий нужную окрестность исходного регулярного выражения. Далее приближенный поиск регулярного выражения ведется уже на основе построенного конечного автомата. Хороший обзор существующих алгоритмов приближенного поиска дан в [6, 13].

Для различных практический приложений крайне важен вопрос о том, насколько большим окажется автомат, с помощью которого будет осуществляться приближенный поиск по регулярному выражению. Такая постановка вопроса приводит нас к необходимости исследования дескриптивной сложности окрестности языка в некоторой метрике (мы, как и многие исследователи, будем рассматривать случай классической метрики Хэмминга; окрестность радиуса г языка Ь в метрике Хэммин-га будем обозначать через <Э{Ь,г)). В [18] кроме собственно алгоритма построения автомата приводится оценка количества, состояний в этом автомате. Однако данный вопрос рассматривается лишь для случая регулярного языка, состоящего из одного слова. В результате можно сформулировать следующую задачу

Задача 1. Оцепить дескриптивную сложность окрестности регулярного языка в метрике Хэмминга.

До этого момента речь шла о дескриптивной сложности конкретных

операций над регулярными языками. Представляется вполне естественным желание получить оценки дескриптивной сложности сразу для некоторого класса операций, сохраняющих регулярность языка. Например, в качестве такого класса можно рассматривать операции, задаваемые конечными трансдьюсерами.

Конечный трансдьюсер (абстрактный конечный автомат, в терминах книги [2]) является модификацией недетерминированного конечного автомата, в которой каждый переход помечен не одним, а двумя словами (возможно, над разными — входным и выходным — алфавитами). На вход трансдьюсера подается некоторое слово. По мере чтения этого слова в автомате трансдьюсера (используя первые слова в каждом переходе) будем последовательно записывать вторые слова соответствующих переходов. В результате на выходе получится некоторое слово над выходным алфавитом, которое будем называть образом исходного входного слова при применении данного трансдьюсера. При помощи конечных трансдьюсеров можно преобразовывать слова, а значит, и целые языки — объединяя образы всех слов языка. Результат применения трансдьюсера г к языку Ь будем обозначать через т(Ь), а количество состояний в трансдьюсере будем обозначать через |т|.

Важное значение для теории конечных трансдьюсеров имеет теорема о том, что образ регулярного языка при применении к нему конечного трансдьюсера остается регулярным языком ([15], теорема 1.6). В нашем случае это позволяет сформулировать следующую задачу:

Задача 2. Оценить дескриптивную сложность применения к регулярному языку конечного трансдьюсера.

Классические алгоритмы приближенного поиска, основанные на рассмотрении окрестности языка в некоторой метрике с фиксированным числом ошибок, не во всех приложениях дают желаемый результат. В [9] предлагается алгоритм (также на основе конечных автоматов) для поиска образца в тексте, который содержит не более чем заданное количество ошибок в каждом блоке заданной длины — окрестность слова или языка, устроенную таким образом, будем называть динамической окрестностью. Если Ь — некоторый язык, ?— максимально допустимое количество ошибок, а £ — длина блока, то соответствующую динамическую окрестность будем обозначать через 0{Ь,г,£). Подобная постановка задачи представляется очень естественной: чем более длинный образец или текст мы обрабатываем, тем большее количество ошибок там может содержаться. Пожалуй, такая постановка задачи актуальней всего для имеющей большое практическое значение проблемы поиска образца в цепочке ДНК. Если имеется некоторый образец ДНК и нужно проверить его вхождение в какую-то цепочку ДНК, то мы должны учитывать,

что в цепочке вполне могли произойти какие-то мутации или погрешности экспериментов, в результате чего отдельные нуклеотиды могли быть изменены. Такие изменения не могут быть очень концентрированными (в противном случае цепочка ДНК разрушится), они должны быть более или менее равномерно распределены по всей длине цепочки. Поиск достаточно длинного образца в такой цепочке необходимо производить с учетом приведенных особенностей. Более подробную информацию об особенностях поиска в цепочках ДНК можно найти в [12, 19].

Естественное желание обобщить поиск одного образца до поиска по регулярному выражению приводит к следующей задаче:

Задача 3. Оценить дескриптивную сложность динамической окрестности регулярного языка.

Целью работы является получение оценок детерминированной и недетерминированной сложности для операций взятия окрестности языка в метрике Хэмминга, применения к языку конечного трансдьюсера и взятия динамической окрестности языка.

Научная новизна. Все результаты диссертации являются новыми.

Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории дескриптивной сложности регулярных языков, а также при разработке алгоритмов приближенного поиска.

Апробация результатов работы. Результаты диссертации докладывались на Международной алгебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шев-рина (Екатеринбург, 2005), Международной конференции по теории языков и автоматов и ее приложениям (Таррагона, 2007), научных семинарах «Алгебраические системы» и «Компьютерные науки» кафедры алгебры и дискретной математики Уральского государственного университета имени А. М. Горького (Екатеринбург, 2007-2009), Российско-индийском семинаре «Алгебра, комбинаторика, сложность» (Екатеринбург, 2009), семинаре кафедры математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М. В. Ломоносова (Москва, 2009).

Публикации. Основные результаты диссертации опубликованы в работах [23]—[27]. Работы [23] и [27] опубликованы в изданиях, входящих в перечень ВАК.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации составляет 78 страниц, библиография содержит 64 наименования.

Краткое содержание работы

Во введении диссертации обсуждается история вопроса и формулируются основные результаты диссертации.

В первой главе диссертации приводятся необходимые определения и вспомогательные утверждения.

Во второй главе диссертации исследуется дескриптивная сложность окрестности регулярного языка в метрике Хэмминга. Для этого в §2.2 приводится конструкция недетерминированного конечного автомата, распознающего окрестность заданного радиуса в метрике Хэмминга данного языка. Эта конструкция позволяет получить верхнюю оценку недетерминированной сложности окрестности регулярного языка. Для доказательства точности этой оценки в §2.3 строится серия регулярных языков над двухбуквенным алфавитом, на которых эта оценка достигается.

При помощи конструкции автомата подмножеств, а также дополнительной информации о внутренней структуре детерминированного автомата, распознающего окрестность регулярного языка, получается верхняя оценка детерминированной сложности этой операции. В §2.4 строится серия регулярных языков над двухбуквенным алфавитом, дескриптивная сложность единичной окрестности которых имеет такой же порядок, что и полученная верхняя оценка.

В §2.5 приведены результаты численных экспериментов, которые показывают, что нижняя оценка детерминированной сложности единичной окрестности языка ближе к точному значению этой величины, чем верхняя оценка.

Основными результатами второй главы являются следующие теоремы.

Теорема 2.1. Пусть Ь — регулярный язык, г > 0. Тогда

пес(0{Ь,г)) < (г + 1)ызс{Ь).

При этом данная оценка является точной, а именно: для любых г > 0 ип> г найдется такой регулярный язык Ь, что пбс (Ь) — пи

шс (0(1, г)) = (г + 1)ш;с(1,).

Теорема 2.2. Пусть Ь — регулярный язык, г > 0. Тогда

бс(0(1, г)) < ^п-2пг+1. При этом для п > 4 найдется такой регулярный язык Ь, что ее(Ь) = п

и

8С(0{Ь, 1)) = 1п • 2" - 2"-4 + п.

Третья глава диссертации посвящена изучению дескриптивной сложности применения конечного трансдьюсера к регулярному языку. В §3.1 отмечается, что постановка задачи об оценке дескриптивной сложности применения конечного трансдьюсера к регулярному языку в терминах количества состояний этого трансдьюсера и дескриптивной сложности этого языка имеет смысл только для нормализованных конечных транс-дьюсеров (т.е. для таких трансдыосеров, у которых переходы подписаны буквами или пустыми словами). Для этого строится пример ненормализованного конечного трансдьюсера, недетерминированная сложность применения которого не выражается через сложность исходного языка и количество состояний в этом трансдьюсере. Важно отметить, что для любого конечного трансдьюсера существует эквивалентный ему нормализованный конечный трансдьюсер.

Далее в §3.2 для заданных конечного нормализованного трансдьюсера и регулярного языка приводится конструкция недетерминированного конечного автомата, который распознает язык, получаемый в результате применения данного трансдьюсера к данному языку. Это позволяет получить верхнюю оценку недетерминированной сложности применения конечного нормализованного трансдьюсера к регулярному языку. Доказательство точности этой оценки осуществляется с использованием результатов второй главы. В §3.3 получена верхняя оценка детерминированной сложности применения конечного нормализованного трансдьюсера к регулярному языку как следствие полученной верхней оценки недетерминированной сложности этой операции.

Основным результатом третьей главы является следующая теорема.

Теорема 3.1. Пусть Ь — регулярный язык, т — нормализованный конечный трансдьюсер. Тогда

пбс{гЩ) < |т| • твс(Ь).

При этом данная оценка является точной, а именно: для любых г > 1 и п > г + 1 найдутся такой регулярный язык Ь и норлшлизованный конечный трансдьюсер т, что пес(£) = п, |т| — г и

пэс(г(1<)) = \т\ • пзе(£).

В четвертой главе диссертации исследуется динамическая окрестность регулярного языка относительно метрики Хэммшга и ее дескриптивная сложность. В §4.1 доказаны некоторые вспомогательные утвер-

ждения относительно динамической окрестности регулярного языка. В §4.2 доказывается, что динамическая окрестность регулярного языка остается регулярным языком. Это позволяет использовать в качестве дескриптивной сложности динамической окрестности недетерминированную сложность. В §4.3 приводится верхняя оценка недетерминированной сложности динамической окрестности регулярного языка.

Основным результатом четвертой главы является следующая теорема.

Теорема 4.2. Пусть Ь — регулярный язык, г, С > 0, г < |. Тогда П5с{0{Ь,г,е)) < 2ее~Ц,/'~г)2 пвс(Ь).

Основные результаты диссертации

• Получена точная верхняя оценка недетерминированной сложности окрестности регулярного языка в метрике Хэммннга.

• Получена верхняя оценка детерминированной сложности окрестности регулярного языка в метрике Хэммннга. Построена серия примеров, показывающих, что полученная оценка точна по порядку для единичной окрестности.

• Получена точная верхняя оценка недетерминированной сложности применения конечного нормализованного трансдьюсера к регулярному языку.

• Получена верхняя оценка недетерминированной сложности динамической окрестности регулярного языка в метрике Хэммннга.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю профессору М. В. Волкову за постановку задач, открытость к общению и неравнодушное отношение к тексту.

Литература

Гасфилд Д., Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология — БХВ-Петербург, 2003.

- 656 с.

Кудрявцев В. Б., Алешин С. В., Подколзин А. С., Введение в теорию автоматов — М.: Наука, 1985. — 320 с.

Левенштейн В. И., Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академии наук СССР — 1965. - Т. 163 (4) - С. 846-848.

Маслов А. Н., Оценки числа состояний конечных автоматов // Доклады Академии наук СССР - 1970. - Т. 194 (6). - С. 12661268.

Маслов А. Н., О циклических перестановках языков // Проблемы передачи информации — 1973. — Т. 9 (4). — С. 81-87.

Baeza-Yates R., Ribeiro В. (eds.), Modern Information Retrieval — Addison-Wesley, 1999. — 544 p.

Birget J.-C., Intersection and union of regular languages and state complexity // Information Processing Letters —1992. — V. 43. — P. 185—

190.

Birget J.-C., Partial orders on words, minimal elements of regular languages, and state complexity // Theoretical Computer Science — 1993. - V. 119 (2). - P. 267-291.

Epifanio C., Gabriele A., Mignosi F., Rcstivo A., Sciortino M., Languages with mismatches // Theoretical Computer Science — 2007.

- V. 385 (1-3). - P.152-166.

Meyer A. R., Fischer M. J., Economy of description by automata, grammars, and formal systems // Proceedings of the Annual Symposium on Foundations of Computer Science — 1971. — P. 188—

191.

11] Moore F., On the bounds for set-state size in the proofs of equivalence between deterministic, nondeterrninistic and two-way finite automata // IEEE Transactions on Computers - 1971. - V. 20. - P. 1211-1214.

121 Myers G., Algorithmic Advances for Searching Biosequence Databases // Suhai S. (ed.) Computational Methods in Genome Research — Plenum Press, 1994. - P. 121-135.

13) Navarro G., NR-grep: a fast and flexible pattern-matching tool // Software — Practice and Experience — 2001. — V. 31. — P. 1265-1312.

14] Rabin M., Scott D., Finite automata and their decision problems // IBM Journal of Research and Development —1959. — V. 3 (2). — P. 114-125.

151 Sakarovitch J., Éléments de théorie des automates — Vuibert, 2003. — 816 p.

161 Salomaa A., On the reducibility of events represented in automata // Annales Academiae Scientiarium Fennicae, Series A, I. Mathematica — 1964. - V. 353.

171 Salomaa K., Descriptional complexity of nondeterrninistic finite automata // Lecture Notes in Computer Science — 2007. — V. 4588. - P. 31-35.

18] Ukkonen E., Finding approximate patterns in strings // Journal of Algorithms - 1985. - V. 6. - P. 132-137.

191 Waterman M., Introduction to Computational Biology: Maps, Sequences and Genomes — Chapman and Hall, 1995. — 448 p.

201 Wu S., Manber U., Fast text searching allowing errors // Communications of the ACM - 1992. - V. 35 (10). - P. 83-91.

211 Yu S., State complexity: recent results and open problems // Fundamenta Informaticae - 2004. - V. 64 (1-4). - P. 471-180.

22] Yu S., Zuang Q., Salomaa K., The state complexities of some basic operations of regular languages // Theoretical Computer Science — 1994. - V. 125. - P. 315-328.

Работы автора по теме диссертации

[23] Поваров Г. А. Регулярность динамической окрестности регулярного языка // Труды института математики и механики — 2009. — Т. 15 (2) - С. 193-201.

[24] Поваров Г. А. Конечные трансдъюсеры и недетерминированная сложность регулярного языка // Уральский государственный университет, Екатеринбург - 2009. — Деп. в ВИНИТИ 21.10.2009 №644-В2009. - 15 с.

[25] Povarov G. State complexity of the conjugate closure of a regular language // Тезисы докладов международной алгебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторо-вича и 70-летию Л. Н. Шеврина — Издательство Уральского университета, Екатеринбург — 2005. — С. 198-199.

[26] Povarov G. Descriptive complexity of the Hamming neighborhood of a regular language // Proc. of Language and Automata Theory and Applications Conference — Universität Rovira i Virgili — 2007. — P. 509520.

[27] Povarov G. Regularity of a dynamic neighborhood of a regular language 11 Proc. of the Steklov Institute of Mathematics — 2009. — V. 267 Suppl. 1. - P. 201-209.

Ризография НИЧ ГОУ ВПО УГТУ-УПИ 620002, г. Екатеринбург, ул. Мира, 19

Введение

0.1 Регулярные языки и конечные автоматы.

0.2 Дескриптивная сложность.

0.3 Содержание диссертации.

0.4 Апробация результатов.

1 Предварительные сведения

2 Дескриптивная сложность окрестности регулярного языка в метрике Хэмминга

2.1 Окрестность языка в метрике Хэмминга.

2.2 Верхние оценки недетерминированной и детерминированной сложности.

2.3 Нижняя оценка недетерминированной сложности

2.4 Нижняя оценка детерминированной сложности.

2.5 Сопоставление оценок детерминированной сложности и результатов экспериментов.

3 Дескриптивная сложность применения конечного тран-сдьюсера

3.1 Конечные трансдьюсеры.

3.2 Недетерминированная сложность применения конечного трансдыосера.

3.3 Детерминированная сложность применения конечного трансдьюсера.

4 Дескриптивная сложность динамической окрестности регулярного языка

4.1 Динамическая окрестность языка.

4.2 Регулярность динамической окрестности регулярного языка

4.3 Верхняя оценка недетерминированной сложности

0.1 Регулярные языки и конечные автоматы

Теория регулярных языков и конечных автоматов является весьма значительной частью общей теории формальных языков. Начало изучения конечных автоматов можно заметить в 40-х гг. в работе Мак-Каллоха и Питса [34], где для моделирования нейронной сети использовалось устройство с конечным набором состояний. С этого момента регулярные языки и конечные автоматы изучаются чрезвычайно интенсивно. Одним из ранних результатов явилась теорема К лини [29], устанавливающая эквивалентность класса языков, задаваемых регулярными выражениями и конечными автоматами, а также появление автомата с выходом в работах Мили [35] и Мура [37], недетерминированных конечных автоматов в работах Рабина и Скота [45] и характеризация регулярных языков при помощи конгруэнции конечного индекса в работах Майхилла [40] и Нерода [43]. В соответствии с иерархией формальных языков, которую в 50-х гг. предложил Хомский [16], регулярные языки относятся к третьему типу (после контекстно-зависимых и контекстно-свободных языков) и являются самым простым классом в этой иерархии.

Регулярные языки, оставаясь довольно простым объектом, способны описывать самые разные системы. Именно поэтому регулярные языки и конечные автоматы с каждым годом находят все больше и больше применений: это и приложения в задачах обработки текста и лексических анализаторах, и использование в вычислениях при помощи ДНК, и применение в задачах параллельной обработки данных, и многое другое.

Классическим способом задания регулярного языка является детерминированный конечный автомат. Такой автомат имеет конечный набор состояний и конечный набор правил, по которым изменяется текущее состояние в зависимости от входного символа. Одно из состояний является начальным, часть состояний объявлены заключительными. Автомат, начиная читать последовательность символов из начального состояния, меняет свое текущее состояние в соответствии со своим набором правил и заканчивает чтение последовательности в некотором состоянии. Если это состояние является заключительным, то последовательность символов принимается, в противном случае — отвергается. Детерминированный конечный автомат в виде подобного управляющего устройства изображен на рисунке 1.

Рис. 1: Пример представления детерминированного автомата в виде управляющего устройства

Одновременно с появлением данного способа задания регулярных языков возник вопрос о том, как много состояний требуется для задания какого-то конкретного языка таким способом. Интуитивно понятно, что чем более сложно устроен язык, тем большее количество состояний потребуется для его описания при помощи детерминированных конечных автоматов.

Другой не менее распространенный способ задания регулярного языка — это регулярное выражение. Выделяют простые регулярные выражения (пустое множество, пустая строка и отдельные буквы) и составные (выражения, полученные с использованием операций — сложения, произведения и итерации). Сумме двух регулярных выражений соответствует объединение слов, удовлетворяющих одному из этих выражений. Произведению двух регулярных выражений соответствует множество слов, каждое из которых составлено из последовательной записи некоторого слова первого и некоторого слова из второго. Итерации регулярного выражения соответствует объединение всех возможных степеней данного выражения, начиная с нулевой (т.е. с пустого слова). С регулярным языком крайне естественно связать минимальную длину регулярного выражения, задающего данный язык, — длина самой компактной текстовой записи регулярного языка в фиксированной нотации. С длиной регулярного выражения прямо связано количество состояний в недетерминированном конечном автомате — автомате, который может проводить вычисления, используя параллельно сразу несколько правил в разных потоках. Таким образом, вполне естественно оценивать сложность языка при помощи минимального размера недетерминированного конечного автомата, который этот язык распознает.

1. Гасфилд Д., Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология — БХВ-Петербург, 2003. — 656 с.

2. Кудрявцев В. В., Алешин С. В., Подколзин А. С., Введение в теорию автоматов — М.: Наука, 1985. — 320 с.

3. Левенштейн В. И., Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академии наук СССР — 1965. Т. 163 (4) — С. 846-848.

4. Лупанов О. В., О сравнении двух типов конечных источников 11 Проблемы кибернетики — 1963. — Вып. 9. — С. 321-326.

5. Маслов А. Н., Оценки числа состояний конечных автоматов // Доклады Академии наук СССР 1970. — Т. 194 (6). — С. 12661268.

6. Маслов А. Н., О циклических перестановках языков // Проблемы передачи информации — 1973. — Т. 9 (4). — С. 81-87.

7. Чашкин А. В., Лекции по дискретной математике — М.: МГУ, 2007. — 261 с.

8. Ananichev D. S., Volkov М. V., Dighaphs admiting only coloring with long synchronizing instructions, в печати.

9. Baeza-Yates R., Ribeiro B. (eds.), Modern Information Retrieval — Addison-Wesley, 1999. — 544 p.

10. Birget J.-C., Intersection and union of regular languages and state complexity // Information Processing Letters — 1992. — V. 43. — P. 185-190.

11. Birget J.-C., Partial orders on words, minimal elements of regular languages, and state complexity // Theoretical Computer Science — 1993. — V. 119 (2). P. 267-291.

12. Calude C., Salomaa K., Yu S., Metric lexical analysis // Lecture Notes in Computer Science — 2001. — V. 2214. — P. 48-59.

13. Campeanu C., Culik K., Salomaa K., Yu S., State complexity of basic operations on finite languages // Lecture Notes in Computer Science- 2001. V. 2214. - P. 60-70.

14. Campeanu C., Salomaa K., Yu S., Tight lower bound for the state complexity of shuffle of regular language J/ Journal of Automata, Lanugages and Combinatorics — 2002. — V. 7. — P. 303-310.

15. Cerny J., Poznamka к homogennym eksperimentom s konecnymi automatami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. — 1964. — V. 14. — P. 208-216.

16. Chomsky N., Three models for the description of language // IRE Transactions on Information Theory — 1956. — V. 2. — P. 113-124.

17. Domaratzki M., State complexity and proportional removals // Journal of Automata, Lanugages and Combinatorics — 2002. — V. 7.- P. 455-468.

18. El-Mabrouk N., On the size of minimal automata for approximate string matching // Institut Gaspard Monge, Universite de Marne-la-Vallee 1997. - V. IGM97-19 (technical report).

19. Epifanio C., Gabriele A., Mignosi F., Restivo A., Sciortino M., Languages with mismatches // Theoretical Computer Science — 2007. V. 385 (1-3). - P. 152-166.

20. Gruber H., Holzer M., Finding lower bounds for nondeterministic state complexity is hard // Lecture Notes in Computer Science — 2006. V. 4036. - P. 363-374.

21. Gruber H., Holzer M., Inapproximability of nondeterministic state and transition complexity assuming P Ф NP // Lecture Notes in Computer Science — 2007. — V. 4588. — P. 205-216.

22. Han Y.-S., Salomaa K., State complexity of union and intersection of finite languages // Lecture Notes in Computer Science — 2007. — V. 4588. P. 217-228.

23. Hopcroft J. E., An nlogn algorithm for minimizing states in finite automaton // Stanford University — 1971. — CS-71-190 (technical report).

24. Hopcroft J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages, and Computation — Addison-Wesley, 2001 — 521 p.

25. Jirasek J., Jiraskova G., Szabari A., Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet // Lecture Notes in Computer Science — 2007. — V. 4588. — P. 254265.

26. Jiraskova G., Magic Numbers and Ternary Alphabet // Lecture Notes in Computer Science — 2009. — V. 5583. — P. 300-311.

27. Jiraskova G., Okhotin A., On the state complexity of operations on two-way finite automata // Lecture Notes in Computer Science — 2008. V. 5257. - P. 443-454.

28. Karhumaki J., Automata and Formal Languages // http://www.math.utu.fi/en/home/karhumak/Automata2007.pdf (электронные материалы лекций) — 2007.

29. Kleene S. С., Representation of events in nerve nets and finite automata // Automata Studies — 1956. — P. 2-42.

30. Kukich K., Techniques for automatically correcting words in text // ACM Computing Surveys 1992. - V. 24 (4). — P. 377-439.

31. Kutrib M., Holzer M., Unary language operations and their nondeterministic state complexity /j Lecture Notes in Computer Science 2003. - V. 2450. — P. 162-172.

32. Kutrib M., Holzer M., State complexity of basic operations on nondeterministic finite automata // Lecture Notes in Computer Science 2003. - V. 2608. — P. 151-160.

33. Kutrib M., Holzer M., Nondeterministic descriptional complexity of regular languages // International Journal of Foundations of Computer Science 2003. - V. 6 (14). - P. 1087-1102.

34. McCulloch W. S., Pitts W., A logical calculus of the ideas immanent in nervous activity // Bulletin of Mathematical Biophysics — 1943. — V. 5. P. 115-133.

35. Mealy G. H., A method for synthesizing sequential circuits j I Bell System Technical Journal — 1955. — V. 34(5). — P. 1045-1079.

36. Meyer A. R., Fischer M. J., Economy of description by automata, grammars, and formal systems // Proceedings of the Annual Symposium on Foundations of Computer Science — 1971. — P. 188191.

37. Moore E. F., Gedanken experiments on sequential machines // Automata Studies — 1956. — P. 129-153.

38. Moore F., On the bounds for set-state size in the proofs of equivalence between deterministic, nondeterministic and two-way finite automata 11 IEEE Transactions on Computers — 1971. — V. 20. — P. 12111214.

39. Myers G., Algorithmic advances for searching biosequence databases // Suhai S. (ed.) Computational Methods in Genome Research — Plenum Press, 1994. — P. 121-135.

40. Myhill J., Finite automata and the representation of events // Wright Patterson AFB, Ohio — 1957. — WADD TR-57-625. — P. 112-137 (technical report).

41. Navarro G., A guided tour to approximate string matching // ACM Computing Surveys — 2001. — V. 33. — P. 31-88.

42. Navarro G., NR-grep: a fast and flexible pattern-matching tool // Software — Practice and Experience — 2001. — V. 31. — P. 12651312.

43. Nerode A., Linear automata transformation // Proceedings of AMS1958. — V. 9. — P. 541-544.

44. Okhotin A., State complexity of linear conjunctive grammars // Journal of Automata, Languages and Combinatorics — 2004. V. 9(2/3). P. 365-381.

45. Rabin M., Scott D., Finite automata and their decision problems // IBM Journal of Research and Development — 1959. — V. 3 (2). — P. 114-125.

46. Sakarovitch J., Elements de theorie des automates — Vuibert, 2003.- 816 p.

47. Salomaa A., On the reducibility of events represented in automata j/ Annales Academiae Scientiarium Fennicae, Series A, I. Mathematica- 1964. V. 353.

48. Salomaa A., Wood D., Yu S., On the state complexity of reversals of regular languages // Theoretical Computer Science —2007. — V. 383 (2-3). — P. 140-152.

49. Salomaa A., Salomaa K., Yu S., State complexity of combined operations // Theoretical Computer Science — 2004. — V. 320 (2-3).P. 315-329.51