Читать онлайн «Конечные автоматы (поведение и синтез)»

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ОСНОВАНИЯ МАТЕМАТИКИ ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1970 КОНЕЧНЫЕ АВТОМАТЫ (ПОВЕДЕНИЕ И СИНТЕЗ) Б. А. ТРАХТЕНБРОТ Я. М. БАРЗДИНЬ ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1970 518 Τ 65 УДК 519. 95 Борис Авраамович Трахтенброт Ян Мартынович Барздинь Конечные автоматы (поведение и синтез) М. , 1970 г. , 400 стр. с илл. Редакторы Б. Ю. Пильчак и Я. А. Карпова Техн. редактор С. Я. Шкляр Корректор Т. А. Панькова Сдано в набор 22/IV 1969 г. Подписано к печати 26/1 1970 г. Бумага 84Х108'/и. Физ. печ. л. 12,5. Условн. печ. л. 21. Уч. -нзд. л. 20,54. Тираж 9000 экз. Т-00137. Цена книги 1 р. 53 к. Заказ № 161. Издательство «Наука». Главная редакция физико-математической литературы, Москва В-71, Леииискнй проспект, 15. Ордена Трудового Красного Знамени Ленинградская типография № 2 Имени Евгении Соколовой Главполиграфпрома Комитета по печати при Совете Министров СССР, Измайловский проспект, 29. 2-2-4 9ЙЙГ ОГЛАВЛЕНИЕ Предисловие , , , . 9 Глава О Введение § 1. Понятие автомата 18 § 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 J 82 § 10. Доказательство теоремы о сильной итерации (теоре- ма 1. 12) 87 § 11. Вероятностные автоматы 94 6 ОГЛАВЛЕНИЕ § 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.