Вопросы оптимальности в теории синхронизируемых автоматов

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

Содержание
Введение

0.1 Синхронизируемые автоматы и гипотеза Черни

0.2 Синхронизируемые автоматы с нулем

0.3 Конечно порожденные синхронизируемые автоматы

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

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

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

1 Медленно синхронизируемые автоматы с нулем и непокрывающие множества

1.1 Непокрывающие множества

1.2 Полу цветочный автомат для конечного множества слов

1.3 Непокрывающие множества и синхронизируемые автоматы
2 Конечно порожденные синхронизируемые автоматы
2.1 Характеризация конечно порожденных синхронизируемых
автоматов
2.2 Алгоритм проверки конечности языка минимальных синхронизирующих слов
2.3 Время работы алгоритма
2.4 Гипотеза Черни для класса конечно порожденных синхронизируемых автоматов
2.5 Верхняя оценка длины минимального синхронизирующего
слова
2.6 Вычислительная сложность задачи проверки конечности
языка минимальных синхронизирующих слов
2.7 Вычислительная сложность в случае постоянного алфавита
3 Некоторые свойства 3-сжимающих и 2-синхронизирующих слов
3.1 Характеризация 2-сжимающих слов
3.1.1 Классификация 2-сжимаемых автоматов
3.1.2 Критерий 2-сжимаемости слова
3.1.3 Критерий в случае одной почти перестановочной буквы

3.1.4 Критерий в случае двухбуквенного алфавита
3.2 Нижняя оценка длины кратчайшего
2-сжимающего слова
3.3 Место языка 2-сжимающих слов в иерархии Хомского
3.4 Характеризация 2-синхронизирующих слов
3.5 Реконструкция 2-сжимающих и 2-синхронизи-
рующих слов по внутренним отрезкам
3.6 Модификация алгоритма распознавания
2-сжимающих слов
Список литературы

Введение
0.1 Синхронизируемые автоматы и гипотеза Черни
В данной работе под словом «язык» понимается формальный язык над фиксированным конечным алфавитом В, т.е. подмножество свободного моноида Е* над Е, а под словом «автомат» - конечный детерминированный автомат с входным алфавитом Е. Такой автомат уА = (С}, Е, 6) определяется заданием конечного множества состояний С) и функции перехода 5 : <2 х Е —* <3- (Отметим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние до £ <3 и множество .Р заключительных состояний. Мы также будем пользоваться этим вариантом определения, когда речь будет идти о языках, распознаваемых автоматами.) Функция 5 естественным образом продолжается на свободный моноид Е*, это продолжение мы также будем обозначать через 5. Таким образом, каждое слово т 6 Е* (в частности каждая буква алфавита Е) порождает преобразование £(_,щ) : <2 —> С} множества С). Имея дело с конечными детерминированными автоматами, мы будем отождествлять слово и) с этим преобразованием. Для слова гн £ Е* и подмножества Б С (£ через Б. 'ш обозначим образ слова ги, т.е. множество (%,ад) | д € 5}.
Автомат у/ — {<2, А, 6) называется синхронизируемым, если существует слово -ш £ А*, переводящее его в одно выделенное состояние, независимо от текущего состояния автомата, т.е. д.ги = г/.ги для всех д, д' £ С}. Любое слово с таким свойством называется синхронизирующим для автомата у А Пример синхронизируемого автомата с четырьмя состояниями приведен на рис. 1. Нетрудно проверить, что слово ги = Ьа3Ьа3Ь синхронизирует этот автомат (более того, ги является кратчайшим синхронизирующим для этого автомата). Данный пример принадлежит словацкому математику Яну Черни, который в 1964 году в работе [21] впервые формально ввел понятие синхронизируемого автомата. Это понятие возникло в рамках классического подхода «умозрительных экспериментов» Мура [46]. Мур и его последователи использовали конечные автоматы для моделирования дискретно работающих устройств (компьютеров). Естественный вопрос в связи с этим следующий: как мы можем восстановить контроль над устройством, не зная его текущего состояния, но наблюдая его поведение в ответ на различные посылаемые ему вход-
УСЛОВИЕ: Синхронизируемый автомат = (<2, В, 5).
ВОПРОС: Конечен ли язык
2.1 Характеризация конечно порожденных синхронизируемых автоматов
Зафиксируем синхронизируемый автомат — {(,'Е,5). Подмножество 5 множества С} называется достижимым, если существует слово ад е Е*, что <5 .ад = 5. Для данного подмножества 5 множества <2 через С (Б) будем обозначать множество всех слов, стабилизирующих Я:
С(5) = {адеЕ* |5.ги = 5}.
Через ЩЗ) обозначим множество всех слов, синхронизирующих 5:
7г(5) = {шеЕ* | |5ад| = 1}.
Заметим, что .5? (.к/) содержится в 7?.(5) для любого подмножества 3.
Лемма 2.1. Для любого слова ад 6 Е* существует целое число 0 > О такое, что ад стабилизирует множество тп(ш) = <2. ги0. Более того, т(ю) - наибольшее подмножество множества с таким свойством.
Доказательство. Рассмотрим подмножества вида (0. ад“ С (0 для всех а > 0. Поскольку С) имеет только конечное число подмножеств, найдутся целые 0 > 0 и 7 > 0, что <2 . = <2 . адй+7. Легко заметить, что
<2 -ад3 Э . ги0+1 2 2 <2 w,,+~, = . ад0.
Следовательно, все включения являются равенствами, в частности, имеем С}. ад*3*1 = <2 иI0. Таким образом, слово ад стабилизирует множество С2. и)0. С другой стороны, рассмотрим произвольное подмножество 6' £ С(й'). Применяя ад, получим
Б = Б.и><ЯС2.и)
Значит, т(ад) - наибольшее подмножество, стабилизируемое словом ад.