ИДЕАЛЬНЫЕ ЯЗЫКИ И СИНХРОНИЗИРУЕМЫЕ АВТОМАТЫ
|
Введение 4
0.1 Копенные автоматы 4
0.2 Синхронизируемые автоматы и гипотеза Черни 6
0.3 Представление идеальных языков синхронизируемыми автоматами 13
0.4 Определения и обозначения 22
0.5 Предварительные сведения о конечно порожденных синхронизируемых автоматах 24
0.6 Предварительные сведения о синтаксической полугруппе
регулярного языка 26
0.7 Предварительные сведения из теории сложности вычислений 27
0.8 Апробация результатов 29
1 Языки синхронизирующих слов медленно синхронизируемых автоматов 31
1.1 Верхняя оценка синхронизационной сложности идеального
языка 32
1.2 Синхронизационная и дескриптивная сложность языков синхронизирующих слов медленно синхронизируемых автоматов 34
1.3 Вопрос о единственности МСА 49
2 Главные идеальные языки и синхронизируемые автоматы 52
2.1 Вопрос о единственности МСА в классе сильно связных
автоматов 53
2.2 Алгоритм построения сильно связного МСА для главного
идеального языка 56
2.3 Доказательство корректности алгоритма 61
2.4 Синхронизационная сложность главного идеального языка 64
2.5 Синтаксическая полугруппа главного идеального языка . . 66
3 Конечно порожденные идеальные языки и синхронизируемые автоматы 75
3.1 Идеальный язык, порожденный Ега 75
3.2 Идеальный язык, порожденный множеством слов постоянной длины 78
3.3 Идеальный язык, порожденный копенным множеством слов 81
3.4 Идеальный язык, порожденный двумя словами 83
4 Вычисление синхронизационной сложности идеальных языков 90
4.1 Принадлежность классу PSPACE 91
4.2 PSPACE-полнота 93
5 Представление регулярных языков синхронизируемыми
автоматами 108
5.1 Левые факторы главных левых идеальных языков 109
5.2 Регулярные языки и синхронизируемые автоматы 114
Список литературы
0.1 Копенные автоматы 4
0.2 Синхронизируемые автоматы и гипотеза Черни 6
0.3 Представление идеальных языков синхронизируемыми автоматами 13
0.4 Определения и обозначения 22
0.5 Предварительные сведения о конечно порожденных синхронизируемых автоматах 24
0.6 Предварительные сведения о синтаксической полугруппе
регулярного языка 26
0.7 Предварительные сведения из теории сложности вычислений 27
0.8 Апробация результатов 29
1 Языки синхронизирующих слов медленно синхронизируемых автоматов 31
1.1 Верхняя оценка синхронизационной сложности идеального
языка 32
1.2 Синхронизационная и дескриптивная сложность языков синхронизирующих слов медленно синхронизируемых автоматов 34
1.3 Вопрос о единственности МСА 49
2 Главные идеальные языки и синхронизируемые автоматы 52
2.1 Вопрос о единственности МСА в классе сильно связных
автоматов 53
2.2 Алгоритм построения сильно связного МСА для главного
идеального языка 56
2.3 Доказательство корректности алгоритма 61
2.4 Синхронизационная сложность главного идеального языка 64
2.5 Синтаксическая полугруппа главного идеального языка . . 66
3 Конечно порожденные идеальные языки и синхронизируемые автоматы 75
3.1 Идеальный язык, порожденный Ега 75
3.2 Идеальный язык, порожденный множеством слов постоянной длины 78
3.3 Идеальный язык, порожденный копенным множеством слов 81
3.4 Идеальный язык, порожденный двумя словами 83
4 Вычисление синхронизационной сложности идеальных языков 90
4.1 Принадлежность классу PSPACE 91
4.2 PSPACE-полнота 93
5 Представление регулярных языков синхронизируемыми
автоматами 108
5.1 Левые факторы главных левых идеальных языков 109
5.2 Регулярные языки и синхронизируемые автоматы 114
Список литературы
Детерминированным конечным, автоматом (ДКА) мы будем называть тройку А = (Д, ЕД), где Д - конечное множество состояний, Е - конечный входной алфавит, а5: Д х Е ^ Д - всюду определенная функция, переходов. Отметим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние д0 6 Д и тожество Р заключительных (или конечных) состояний. Мы также будем пользоваться этим вариантом определения и писать А = (Д, Е,5,д0,Р), когда речь будет идти о языках, распознаваемых автоматами. Для заданного ДКА А = (Д, Е,фд0,Р) положим Р[А] = {ш | щ .ш 6 Р}, при этом будем говорить, что язык Р[А] принимается (или распознается) автоматом А. Язык называется регулярным, если он распознается некоторым детерминированным конечным автоматом. Всюду в данной работе будем использовать слово “автомат" в качестве синонима термина “детерминированный конечный автомат".
Конечный автомат является довольно естественной моделью дискретно работающего устройства, которая находит применение во множестве областей. Прообраз такой модели был представлен в работе нейрофизиологов МакКаллока и Питтса [36], написанной в 1943 году. В пей автоматы были введены как упрощенная модель функционирования нейронов. Примечательно, что в этой работе также были заложены основы машинного обучения. Позднее Клини [33] уточнил и развил модель, предложенную МакКаллоком и Питтсом, чем и заложил основы теории автоматов, как математической дисциплины. Именно в работе [33] был получен основополагающий результат теории автоматов, утверждающий совпадение класса языков, распознаваемых конечными автоматами, с классом языков, задаваемых при помощи регулярных операций - объединения, произведения и итерации. Таким образом, Клини рассматривал конечные автоматы как распознаватели формальных языков. Исторически же первую модель распознавателя языков предложил в 1936 году английский математик Тьюринг [63]. Машина Тьюринга (которая является более общим объектом, нежели конечный автомат) могла по только распознавать строки символов, по и преобразовывать одни строки в другие. На ее основе Тьюринг спроектировал один из первых в мире компьютеров. Более того, термин “компьютер" в его современном значении впервые употребил именно Тьюринг. Благодаря развитию вычислительной техники теория автоматов пополнилась многочисленными приложениями. На сегодняшний день теория автоматов лежит в основе теории компиляторов и формальной верификации программ.
Теория автоматов также имеет глубокие взаимосвязи с логикой и алгеброй. Мысль о том что логические высказывания могут быть изучены в терминах конечных автоматов была высказана еще Тьюрингом в работе [63], написанной в 1937 году. Эта мысль была поддержана и развита фон Нейманом в работе [66], где автомат, моделирующий логическое высказывание, представлялся “черным ящиком" с конечным числом входов и конечным числом выходов. Операция, выполняемая черным ящиком, в таком случае задается законом, которые определяет, какие выходы активируются в ответ на посылаемые тем или иным входам сигналы. Отличительной особенностью модели фон Неймана является отсутствие информации о внутреннем устройстве автомата. Идею рассмотрения автомата как “черного ящика" можно обнаружить и в работе Мура [37] «Gcdankcn-expcrimcnts on Sequential Machines», опубликованной в 1956 году. Автоматом Мура, называется конечный автомат с множеством со-стояний Q, входным алфавитом Е и функцией переходов ¿, дополненный конечным множеством выходных символов Д, а также выходной функцией д, которая ставит в соответствие каждому состоянию q G Q символ алфавита Д. Таким образом, автомат Мура, находящийся в некотором состоянии q G Q при чтении входного символа a G Е не только переходит в новое состояние p = ¿(q, а), по и выводит символ д(р). Для Мура такой автомат служил моделью дискретно работающих устройств, о внутренней конструкции которых ничего не известно. В связи с этим, главный вопрос, интересовавший Мура, состоит в следующем. Предположим, над некоторым устройством потерян контроль. Какую последовательность входных символов необходимо подать на вход устройства, чтобы по наблюдаемым выходным символам можно было однозначно определить состояние, в котором будет находится устройство? В работе [37] такая последовательность входных символов называется экспери-ментом, при этом длиной эксперимента естественно назвать количество символов последовательности. Отметим, что эксперименты Мура имели адаптивный характер, т.е. каждый следующий символ входной последовательности зависел от уже полученной последовательности выходных символов. Одним из важнейших результатов работы Мура является полученная оценка длины кратчайшего эксперимента, позволяющего определить состояние устройства в конце эксперимента. В [37] показано, что для произвольного автомата Мура с п состояниями существует эксперимент длины не больше которым можно определить состояние автомата в конце эксперимента. С практической точки зрения длина эксперимента определяет, насколько быстро можно восстановить контроль над устройством.
Конечный автомат является довольно естественной моделью дискретно работающего устройства, которая находит применение во множестве областей. Прообраз такой модели был представлен в работе нейрофизиологов МакКаллока и Питтса [36], написанной в 1943 году. В пей автоматы были введены как упрощенная модель функционирования нейронов. Примечательно, что в этой работе также были заложены основы машинного обучения. Позднее Клини [33] уточнил и развил модель, предложенную МакКаллоком и Питтсом, чем и заложил основы теории автоматов, как математической дисциплины. Именно в работе [33] был получен основополагающий результат теории автоматов, утверждающий совпадение класса языков, распознаваемых конечными автоматами, с классом языков, задаваемых при помощи регулярных операций - объединения, произведения и итерации. Таким образом, Клини рассматривал конечные автоматы как распознаватели формальных языков. Исторически же первую модель распознавателя языков предложил в 1936 году английский математик Тьюринг [63]. Машина Тьюринга (которая является более общим объектом, нежели конечный автомат) могла по только распознавать строки символов, по и преобразовывать одни строки в другие. На ее основе Тьюринг спроектировал один из первых в мире компьютеров. Более того, термин “компьютер" в его современном значении впервые употребил именно Тьюринг. Благодаря развитию вычислительной техники теория автоматов пополнилась многочисленными приложениями. На сегодняшний день теория автоматов лежит в основе теории компиляторов и формальной верификации программ.
Теория автоматов также имеет глубокие взаимосвязи с логикой и алгеброй. Мысль о том что логические высказывания могут быть изучены в терминах конечных автоматов была высказана еще Тьюрингом в работе [63], написанной в 1937 году. Эта мысль была поддержана и развита фон Нейманом в работе [66], где автомат, моделирующий логическое высказывание, представлялся “черным ящиком" с конечным числом входов и конечным числом выходов. Операция, выполняемая черным ящиком, в таком случае задается законом, которые определяет, какие выходы активируются в ответ на посылаемые тем или иным входам сигналы. Отличительной особенностью модели фон Неймана является отсутствие информации о внутреннем устройстве автомата. Идею рассмотрения автомата как “черного ящика" можно обнаружить и в работе Мура [37] «Gcdankcn-expcrimcnts on Sequential Machines», опубликованной в 1956 году. Автоматом Мура, называется конечный автомат с множеством со-стояний Q, входным алфавитом Е и функцией переходов ¿, дополненный конечным множеством выходных символов Д, а также выходной функцией д, которая ставит в соответствие каждому состоянию q G Q символ алфавита Д. Таким образом, автомат Мура, находящийся в некотором состоянии q G Q при чтении входного символа a G Е не только переходит в новое состояние p = ¿(q, а), по и выводит символ д(р). Для Мура такой автомат служил моделью дискретно работающих устройств, о внутренней конструкции которых ничего не известно. В связи с этим, главный вопрос, интересовавший Мура, состоит в следующем. Предположим, над некоторым устройством потерян контроль. Какую последовательность входных символов необходимо подать на вход устройства, чтобы по наблюдаемым выходным символам можно было однозначно определить состояние, в котором будет находится устройство? В работе [37] такая последовательность входных символов называется экспери-ментом, при этом длиной эксперимента естественно назвать количество символов последовательности. Отметим, что эксперименты Мура имели адаптивный характер, т.е. каждый следующий символ входной последовательности зависел от уже полученной последовательности выходных символов. Одним из важнейших результатов работы Мура является полученная оценка длины кратчайшего эксперимента, позволяющего определить состояние устройства в конце эксперимента. В [37] показано, что для произвольного автомата Мура с п состояниями существует эксперимент длины не больше которым можно определить состояние автомата в конце эксперимента. С практической точки зрения длина эксперимента определяет, насколько быстро можно восстановить контроль над устройством.
Подобные работы
- ИДЕАЛЬНЫЕ ЯЗЫКИ
И СИНХРОНИЗИРУЕМЫЕ АВТОМАТЫ
Авторефераты (РГБ), математика. Язык работы: Русский. Цена: 2200 р. Год сдачи: 2015