Трахтенброт Б.Я., Барздинь Я.М. Конечные автоматы (поведение и синтез)

ОГЛАВЛЕНИЕ

Предисловие 9

Глава О Введение

§ 1. Понятие автомата.............. 13

§ 2. Варианты автоматов............. 18

§ 3. Автоматы и графы.............. 24

§ 4. Некоторые терминологические разъяснения..... 29

§ 5. Обзор содержания глав I—V.......... 34

Замечания.................. 41

Глава I

Поведение автоматов без выхода

§ 1. Представление языков и сверхъязыков в автоматах 44

§ 2. Взаимозамещаемость............48

§ 3. Различимость слов и сверхслов.........52

§ 4. Распознавание свойств конечных автоматов.... 57

§ 5. Проекции, источники, макроисточники......61

§ 6. Операции над источниками (макроисточниками) и над

представляемыми ими языками (сверхъязыками).. 68

§ 7. Детерминизация источников. Операции, не выводящие из класса языков, представимых в конечных автоматах....................73

§ 8. Детерминизация макроисточников. Операции, не выводящие из класса сверхъязыков, представимых в конечных автоматах...............80

§ 9. Доказательство теоремы о конкатенации (теорема 1.11) 82

§ 10. Доказательство теоремы о сильной итерации (теорема 1.12)..................87

§ 11. Вероятностные автоматы...........94

§ 12. Грамматики и автоматы............ 100

Дополнения, задачи, примеры........... 108

Замечания......... 113

Глава II

Поведение автоматов с выходом

§ 1. Предвосхищение.............. 114

$ 2. Память (вес)................ 121

§ 3. Эквивалентные автоматы........... 126

§ 4. Сравнение веса оператора с весом реализующего его

автомата................. 131

§ 5. Представление языков (сверхъяаыков) и реализация

операторов. Проблема униформизации...... 136

§ 6. Еще раз о распознавании свойств конечных автоматов 142

§ 7. Игры, стратегии и операторы без предвосхищения..147

§ 8. Игровая интерпретация проблемы униформизации.. 153

§ 9. Порядковые векторы и порядковые стратегии. Леммы 156

§ 10. Теоремы о порядковых стратегиях........ 159

§ 11. Спектры достижимости и различимости...... 163

§ 12. Спектры операторов и реализующих их автоматов.. 168

§ 13. Параметры конечного автомата и его поведения.. 175

Дополнения, задачи............... 183

Замечания.................. 187

Глава III Метаязыки

§ 1. Предварительные примеры и задачи....... 189

§ 2. Обсуждение примеров. Формулировка проблемы.. 192

§ 3. Метаязыки источников (макроисточников), деревьев и

грамматик................ 195

§ 4. Метаязык регулярных формул......... 199

§ 5. Метаязык общерегулярных формул....... 205

§ 6. Логический метаязык И............ 208

§ 7. Выразительность логического метаязыка И..... 216

§ 8. Нормальная форма............. 222

§ 9. Синтез автомата, который представляет сверхъязык,

определяемый И-формулой........... 227

§ 10. Синтез автомата по условиям, предъявляемым к оператору или к языку............. 234

§ 11. Случаи, когда алгоритм синтеза невозможен.... 237

Дополнения, задачи...............244

Замечания................. 247

Глава IV

Расшифровка автоматов

§ 1. Введение.................250

§ 2. Расшифровка относительных «черных ящиков»... 261

§ 3. Частотные критерии. Сложность расшифровки почти

всех относительных «черных ящиков»......269

§ 4. Общие замечания о расшифровке абсолютных «черных

ящиков».................275

§ 5. Итеративные алгоритмы...........278

§ 6. Расшифровка абсолютных «черных ящиков» с любой наперед заданной частотой посредством кратных алгоритмов.................286

§ 7. Оценка сложности равномерной расшифровки... 293

§ 8, Оценка сложности расшифровки (неравномерной).

Формулировка основного результата.......300

§ 9. Доказательство теоремы 4.8..........305

§ 10. Расшифровка абсолютных «черных ящиков» с любой наперед заданной частотой посредством простых алгоритмов..................307

§ 11. Оценка сложности расшифровки (неравномерной) в

случае простых алгоритмов..........315

Дополнения, задачи................326

Замечания................. 333

Глава V

Статистические оценки параметров и спектров автоматов

§ 1. Равномерная статистическая оценка степени различимости..................334

§ 2. Равномерная статистическая оценка спектра насыщения 348

§ 3. Стохастическая процедура построения автоматных графов...................351

§ 4. Статистическая оценка спектра достижимости для автоматных графов...............354

§ 5. Статистическая оценка диаметра. Формулировка основного результата...............357

§ 6. Вспомогательные утверждения из теории вероятностей

§ 7. Доказательство основной леммы.........

§ 8. Нижняя статистическая оценка высоты автоматных

графов..................

§ 9. Статистическая оценка спектра достижимости, степени

достижения и степени восстановления автоматов...

Замечания.............

Литература..................

Предметный указатель................