СОДЕРЖАНИЕ

Введение .......................................................................…….........................................….... 5
1. Основы теории формальных грамматик ......................................................................…... 6
1.1. Основные понятия теории автоматов ..............................................................…............ 6
1.2. Основные понятия теории формальных грамматик ..........................……........................ 8
1.3. Классификация языков по Хомскому...............................................................……....... 11
1.4. Распознающие устройства и автоматы.................................................…...........…....... 13
1.4.1. Концепция порождения и распознавания ...........................................…..............…... 14
1.4.2. Распознающие, порождающие и преобразующие формальные грамматики................ 16
1.5. Автоматы и формальные языки .....................................................……......................... 18
1.5.1. Понятие об информации и ее преобразованиях .......................................................... 18
1.5.2. Преобразование алфавитной информации ....................................……...................... 20
1.5.3. Способы задания автоматов ..............................................................…............…...... 21
Контрольные вопросы ............................................................................................……….. 25
2. Машины Тьюринга ...............................................................…….................................... 25
2.1. Основные понятия .........................................................................……........................ 25
2.2. Машины Тьюринга с двумя выходами ..........................................……......................... 27
2.3. Машины Тьюринга и линейно-ограниченные автоматы ............................................... 29
2.4. Автоматы с магазинной памятью и бесконтекстные языки ..............….......................... 30
2.4.1. Автоматы с магазинной памятью ........................................……................................ 30
2.4.2. Бесконтекстные (контекстно-свободные) языки ......................................................... 32
Контрольные вопросы ..............................................................…….................................... 33
3. Абстрактный конечный автомат ....................................................................……........... 33
3.1. Абстрактная теория автоматов ......................................................…...........….............. 33
3.1.1. Модель дискретного преобразователя Глушкова В.М ................................................ 33
3.1.2. Понятие об абстрактном автомате и индуцируемом им отображении ........................ 34
3.2. Представление событий в автоматах........................................……............................... 36
3.2.1. Автоматные отображения и события ........................................……........................... 36
3.2.2. Представление событий в автоматах ...........................................….............…........... 38
3.2.3. Регулярные языки и конечные автоматы ....................................…....................……. 39
3.3. Алгоритм синтеза конечных автоматов .............................……..................................... 40
3.3.1. Основной алгоритм синтеза конечных автоматов .................…….............................. 40
3.3.2. Усовершенствованный основной алгоритм синтеза конечных автоматов................... 45
3.4. Автоматы Мили и Мура .......................................................…….................................. 49
3.4.1. Автомат Мили ..................................……................................................................... 49
3.4.2. Автомат Мура ....................................................................……................................. 52
3.4.3. Получение неполностью определенных (частичных) автоматов ................................. 53
3.5. Синтез автоматов по индуцируемым ими отображениям .............................................. 53
3.5.1. Общий метод решения задачи ..................................................……........................... 53
3.5.2. Синтез автомата Мили ...........................................................................……............. 55
3.5.3. Синтез автомата Мура…………………………………………..................……………... 57
Контрольные вопросы……………………………………………………..................………….. 58
4. Структурный конечный автомат ...................................................................................... 58
4.1. Основные понятия структурной теории автоматов ..................…................................. 58
4.2. Композиция автоматов и структурные схемы .........................…................................... 61
4.3. Условия корректности и правильности построения схем ........……............................... 63
4.4. Канонический метод структурного синтеза автомата ..................…….......................... 67
4.4.1. Основная задача теории структурного синтеза автоматов ............….......................... 67
4.4.2. Теорема о структурной полноте ................................................…...........….............. 69
4.4.3. Комбинационная часть автомата. Синтез схемы автомата ............................….......... 71
4.5. Кодирование состояний. Гонки в автомате ...........................................……................ 73
4.6. Построение комбинационной схемы автомата …………………….................….………. 75
Контрольные вопросы............................……………………………….............….................. 79
5. Микропрограммирование .................................................................……........................ 79
5.1. Принципы микропрограммного управления ..............................……............................ 80
5.2. Система команд автоматов, реализующих выполнение алгоритма .................…........... 81
5.3. Набор операций автомата .........................................................................……............. 82
5.4. Состав и назначение элементов блок-схемы ............................................…….............. 83
5.5. Общий алгоритм функционирования ………………………………....................……….. 84
5.6. Основные характеристики автоматов ....................................................……................ 84
5.7. Устройство управления микропрограммным автоматом .............................….............. 85
5.8. Формирование адреса микрокоманд ............................................…...........…............... 87
Контрольные вопросы………………………………………….………………..................……. 91
6. Проблемы отображения времени при проектировании ..........…...................................... 91
6.1. Модель тактируемого дискретного автомата ......................……................................... 91
6.2. Выбор параметров тактирующих сигналов ................................….............…............... 93
6.3. Сравнение способов тактирования автоматов ...........................…............…................ 94
6.4. Абсолютная и относительная шкала времени ...........................................……............. 95
6.5. Характеристики сигналов в абсолютной шкале времени ............................……........... 96
6.6. Характеристики сигналов в относительной шкале времени ...……............................... 99
Контрольные вопросы……………………………………………….……................…………. 101
7. Сети Петри .......................................................................................…....................….. 101
7.1. Назначение и общая характеристика сетей Петри ....................................................... 101
7.2. Структура и способы представления сетей Петри ............................................……… 103
7.2.1. Структура сетей Петри ............................................................................................. 104
7.2.2. Графы сетей Петри ................................................................................................... 105
7.2.3. Маркировка сетей Петри ........................................……........................................... 106
7.2.4. Работа сетей Петри.....................................................……....................................... 107
7.3. Анализ сетей Петри ..……........................................................................................... 108
7.3.1. Безопасность сети Петри…....................................................................................... 108
7.3.2. Анализ живучести (сохранения) сетей Петри …....................................................... 109
7.3.3. Активность сети Петри .......................................…….............................................. 111
7.3.4. Достижимость и покрываемость .............................…….......................................... 112
7.4. Моделирование алгоритмов с помощью сетей Петри ......…........................................ 114
7.5. Расширенные сети Петри ....................................................……................................ 118
7.6. Сети Петри и регулярные языки .............................................……............................. 120
7.7. Преобразование конечного автомата в сеть Петри ......................….…........................ 121
7.8. Разработка модели сложения двух чисел с плавающей запятой ........................…....... 124
Контрольные вопросы………………………………………………………................……….. 126
Заключение…………………………………………………………………….................……... 126
Приложение………………………………………………………………….................……….. 127
Предметный указатель……………………………………………………...............………….. 133
Библиографический список…………………………………………...….................………… 134