Идеальные языки и синхронизируемые автоматы

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

Содержание
Введение
0.1 Коночные автоматы
0.2 Синхронизируемые автоматы и гипотеза Черни
0.3 Представление идеальных языков синхронизируемыми автоматами
0.4 Определения и обозначения
0.5 Предвари гельные сведения о конечно порожденных синхронизируемых автоматах
0.6 Предварительные сведения о синтаксической полугруппе
регулярного языка
0.7 Предварительные сведения из теории сложности вычислений
0.8 Апробация результатов
1 Языки синхронизирующих слов медленно синхронизируемых автоматов
1.1 Верхняя оценка синхронизационной сложности идеального
языка
1.2 Синхронизационная и дескриптивная сложность языков син-
хронизирующих слов медленно синхронизируемых автоматов
1.3 Вопрос о единственности МСА
2 Главные идеальные языки и синхронизируемые автоматы
2.1 Вопрос о единственности МСА в классе сильно связных
автоматов
2.2 Алгоритм построения сильно связного МСА для главного
идеального языка
2.3 Доказательство корректности алгоритма
2.4 Синхронизационная сложность главного идеального языка
2.5 Синтаксическая полугруппа главного идеального языка
3 Конечно порожденные идеальные языки и синхронизируемые автоматы
3.1 Идеальный язык, порожденный Ч'
3.2 Идеальный язык, порожденный множеством слов постоянной длины

3.3 Идеальный язык, порожденный конечным множеством слов 81 •3.4 Идеальный язык, порожденный двумя словами
4 Вычисление синхронизационной сложности идеальных языков
4.1 Принадлежность классу РБРАСЕ
4.2 Р Б РАСЕ-полнота
5 Представление регулярных языков синхронизируемыми автоматами
5.1 Левые факторы главных левых идеальных языков
5.2 Регулярные языки и синхронизируемые автоматы
Список литературы

Введение
0.1 Конечные автоматы
Детерминированным конечным, автоматом (ДКА) мы будем называть тройку л/ = {О, Е,й), где <5 - конечное множество состояний. Е - конечный входной алфавит. ад: (5 х Е —» <3 - всюду определенная функция переходов. Отмстим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние у0 € (} н множество Д заключительных (или конечных) состояний. Мы также будем пользоваться этим вариантом определения и писать .е/ = ((^, Е. <5, <70, Т), когда речь будет идти о языках, распознаваемых автоматами. Для заданного ДКА ,й/ = {<5. Е. д. до. К) положим Ь[.в/] = {«; | д0 ■ ш € К}, при этом будем говорить, что язык 1я/ принимается (или распознается,) автоматом .й/. Язык называется регулярным, если он распознается некоторым детерминированным конечным автоматом. Всюду в данной работе будем использовать слово "автомат” в качестве синонима термина “детерминированный конечный автомат”.
Конечный автомат является довольно естественной моделью дискретно работающего устройства, которая находит применение во множестве областей. Прообраз такой модели был представлен в работе нейрофизиологов МакКаллока и Питтса [361, написанной в 1943 году. В ней автоматы были введены как упрощенная модель функционирования нейронов. Примечательно, что в этой работе также были заложены основы машинного обучения. Позднее Клини [33] уточнил и развил модель, предложенную МакКаллоком и Питтсом, чем и заложил основы теории автоматов, как математической дисциплины. Именно в работе [33| был получен основополагающий результат теории автоматов, утверждающий совпадение класса языков, распознаваемых конечными автоматами, с классом языков, задаваемых при помощи регулярных операций -объединения, произведения и итерации. Таким образом, Клини рассматривал конечные автоматы как распознаватели формальных языков. Исторически же первую модель распознавателя языков предложил в 1936 году английский математик Тьюринг [63]. Машина Тыоринга (которая является более общим объектом, нежели конечный автомат) могла не только распознавать строки символов, но и преобразовывать одни строки в другие. На ее основе Тьюринг спроектировал один из первых в

распознающим язык синхронизирующих слов автомата Черни при любом п > 1. Таким образом, 8с(йуа(^’Г1)) — 2п п. Из этого равенства мы получим, как следствие, что гс(8уп(^п)) = п. Отметим, что серия п-автоматов, придуманная Черни [20], оказывается датеко не единственным примером той ситуации, когда минимальный автомат, распознающий данный идеальный язык, содержит экспоненциально больше состояний чем некоторый МСА для этого языка В подтверждение этого факта мы рассмотрим несколько примеров идеальных языков, которые являются языками синхронизирующих слов медленно синхронизируемых автоматов. Рассматриваемые серии автоматов взяты
Введем некоторые обозначения, которые будут использоваться только в данной главе. Пусть дан п-автомат «с/ = (<3,Е.<5). Определим расстояние <1(р.д) между различными состояниями р и д следующим образом (без ограничения общности считаем, что р < д):
Теперь можно определить естественным образом значение (1(11) для неодноэлементного подмножества 11 V О равенством
Автоматом Черни называется п-автомат 8/?п = (С^. Е. 8) (см. рис. 4) с множеством состояний (1) — {0,1,. .и — 1}. входным атфавиюм Е = {о,Ь} и функцией переходов 5. определенной следующим образом.
Предложение 1.4. зс(3уп(‘«?71)) = 2" — п для всякого п > 3.
Доказательство. По автомату Черни 9?п = (СД'Е.б) строим его автомат подмножеств Р(^п) = (2®, Е. (5, Т1)
Сначала проверим, что всякое непустое подмножество Н С О достижимо из начального состояния С?. Индукция по к — |#| Для Н — п утверждение очевидно: множество всех состояний <2 автомата сё’п является начальным состоянием 'Р(<ё’п). Предположим, что любое подмножество мощности 1 < к < п достижимо. Покажем, что тогда достижимы все подмножества II мощности |Д| -к-1. Пусть II = {Р.Р2.......Рк-}: И Рг < Ргт 1 ДЛЯ БСЄХ 1 < I < к ~ 2.
Если II = {0.1, .... к — 2}. тогда II достижимо из IV = {0,1 к — 2. п — 1}.
поскольку IIі .а = II В противном случае существует положительное число
из [1].
<1(р, д) = тш{д — р. п + р — д)

ніш , <Чр- ч)