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

• Автор: Поваров, Григорий Андреевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Екатеринбург
• Количество страниц: 78 с.

Содержание
Введение
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.
о Ъ а Ъ Ь Ъ а а

Состояния Правила перехода
0 12 3 а : 0 —> 1 Ь : 0 ->
<§> 1 2 1 -»
* 2 —> 3 2 —*
3 -> 1 3 ->
Рис. 1: Пример представления детерминированного автомата в виде управляющего устройства
Одновременно с появлением данного способа задания регулярных языков возник вопрос о том, как много состояний требуется для задания какого-то конкретного языка таким способом. Интуитивно понятно, что чем более сложно устроен язык, тем большее количество состояний потребуется для его описания при помощи детерминированных конечных автоматов.
Другой не менее распространенный способ задания регулярного языка — это регулярное выражение. Выделяют простые регулярные выражения (пустое множество, пустая строка и отдельные буквы) и составные (выражения, полученные с использованием операций — сложения, произведения и итерации). Сумме двух регулярных выражений соответствует объединение слов, удовлетворяющих одному из этих выражений. Произведению двух регулярных выражений соответствует множество слов, каждое из которых составлено из после-

Нп, является важным экстремальным примером для теории неотрицательных матриц [53] и теории синхронизируемых автоматов [8]. Нам не известно является ли это случайным совпадением или существует какая-то скрытая взаимосвязь между экстремальными свойствами автомата Нп в различных областях.
Через НАгп обозначим автомат, полученный из Нп так, как это описано в лемме 2.1:
ЯЛГ„= ([0,2п),Е,5;,0,{0,п}),

{q + 1, {0, те + 1}, если q — п — 1, d — а,
{!>«}, если q — n — 1, d — Ъ,
{4 + 1}> если п < q < 2п — 1, d £ Е.
М, если q = 2те — 1, d = а,
{п + 1}, если q = 2те — 1, d = b.
В соответствии с леммой 2.1 автомат HNn распознает 1-окрестность 0(L(Hn), 1). Через HD„ обозначим детерминированный автомат, полученный из HNn при помощи стандартной конструкции автомата подмножеств:
HDn= (21°’2п),£,Д„,{0},Яп),

Дn(P,d) = 6'n(p,d) для всех Р С 20,2п d € Е;

Fn = {F С 2[0-2n) I О £ Р или те £ Р}.
Зафиксируем параметр те и будем в дальнейшем использовать 5' вместо 6'п, А вместо Лп и F вместо Fn.
Множество Р С [0, 2те) будем называть (нетривиально) достижи-