Универсальные синхронизирующие и универсальные сжимающие слова

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

1 Введение
1.1 Синхронизируемость и сжимаемость
1.2 Универсальные синхронизирующие слова
1.3 Универсальные сжимающие слова
1.4 Апробация результатов
2 Разрешимость задачи распознавания сжимающих слов
3 Алгоритм распознавания сжимающих слов
3.1 Предварительные сведения и определения
3.1.1 Фишки и дырки
3.1.2 Послойное представление
3.1.3 Строение слоя
3.1.4 Строение слоя п-собственного автомата
3.1.5 Метки состояний и роли букв
3.1.6 Основа
3.1.7 Операции по изменению основы
3.1.8 Вычисления по основе
3.2 Алгоритм
3.2.1 Общее описание алгоритма
3.2.2 Проверка слова на п-полноту
3.2.3 Генерация ролей букв
3.2.4 Распределение ролей и начало рекурсии
3.2.5 Шаг рекурсии (разбиение на подклассы)
3.2.6 Классы автоматов, не требующие разбиения
3.2.7 Корректность
3.3 Неизоморфность рассматриваемых автоматов
3.4 Время работы алгоритма
4 Алгоритмы поиска и построения синхронизирующих и сжимающих слов
4.1 Переборный алгоритм поиска кратчайших синхронизирующих
слов
4.2 Поиск сжимающих слов
4.3 Распознаватель слов, синхронизирующих автомат
4.4 Алгоритм построения синхронизирующих слов через пересечение языков
4.5 Результаты
5 Зеркальный образ 2-синхронизирующих слов

6 Заключение
Список литературы

1 Введение
1.1 Синхронизируемость и сжимаемость
Детерминированным конечным автоматом (или кратко ДКА) мы будем называть тройку — (<3,£, <5), где <5 — конечное множество состояний, £ — конечный входной алфавит, и 5 — всюду определенная функция переходов, действующая из (3 х £ в <3- Действие букв из £ на множество состояний <3, определяемое функцией переходов 6, естественным образом расширяется до действия слов из свободного £-порожденного моноида £* с пустым словом є; последнее действие будем также обозначать через 6. Для произвольного слова V Є £* и произвольного Ті С <3 мы определим действие словом V на множество Я следующим образом: 5(Я,у) = {5(д,и)д Є Л}. Дефектом действия слова V на автомат з? назовем = |<3| — |<5(<3,г>)|.
ДКА & = ((3,2, <5) называется синхронизируемым, если действие некоторого слова ш € £* отображает все состояния этого автомата в некоторое одно состояние, т. е. существует состояние р Є (3 такое, что для всех состояний д Є <3 выполняется <5(д, т) = р; такое слово ги будем называть синхронизирующим словом для автомата
Рис. 1: Автомат Черни с 4 состояниями
На рис. 1 представлен пример синхронизируемого автомата. Легко проверить, что любое состояние этого автомата словом аЪ3аЬ3а отображается в состояние 2, т. е. слово аЬ3аЬ3а является синхронизирующим словом для данного автомата. Отметим, что у любого синхронизируемого автомата существует бесконечно много синхронизирующих слов, так как если мы припишем к синхронизирующему автомат слову в начало и в конец любые слова, то полученное слово по-прежнему будет синхронизировать этот автомат. Оказывается, что слово аЬ3аЬ3а не только является синхронизирующим словом для автомата Черни с 4 состояниями, но еще и кратчайшим с данным свойством.
Что же хорошего в синхронизирующем автомат слове и почему здесь

находятся в одном классе эквивалентности, в этом же классе находятся состояния #1 и <72 слоя с. Но как мы видим из определения отношения Е, в каждом классе эквивалентности имеется не более одного представителя слоя с. Противоречие.
Рис. 18: Некорректное добавление е-перехода

Рассматривая по очереди в качестве состояния 1 все состояния слоя а, удовлетворяющие условию леммы 3.8, мы добавляем к основе В® новый е-пе-реход (.?!, <) , получая конструкции В, В, /?^1], которые в силу леммы 3.5 являются основами и сохранили распределение ролей.
(а) (б) (в)
Рис. 19: Варианты добавления с-перехода в существующее состояние (б, в). В варианте (в) был добавлен еще один е-переход, необходимый для транзитивности.
После того, как мы определили е-переход для состояния а і и получили множество основ В. В. ..., , мы должны проделать ту же операцию
для состояния ад и каждой из основ В. В В]пх. В результате мы получим множество основ В. В..., В'^п?. И так далее, пока не проделаем эту операцию для состояния а*.