Читать онлайн «Введение в теорию конечных автоматов»

Н. Е. КОБРИНСКИЙ и Б. А. ТРАХТЕНБРОТ ВВЕДЕНИЕ В ТЕОРИЮ КОНЕЧНЫХ АВТОМАТОВ Ш ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1962 АННОТАЦИЯ В последние годы повсеместно и с большой интен- интенсивностью ведутся работы по созданию и применению различных автоматических систем дискретного действия для переработки информации. Они лежат в основе быстродействующих цифровых вычислительных машин, автоматических устройств для управления объектами и систем, моделирующих деятельность живого организ- организма (так называемых роботов). Производство кибернети- кибернетических автоматов растет быстрыми темпами, непре- непрерывно расширяются области их применения. Книга посвящена изложению общих вопросов теории автоматов дискретного действия, имеющих конечную память, которые называются конечными автоматами. Изложению теории предпосылаются краткие сведения по алгебре логики и логике предикатов, необходимые для решения задач анализа и синтеза автоматов. Опи- Описываются физические элементы: электронно-ламповые, полупроводниковые и магнитные, осуществляющие про- простейшие логические операции и являющиеся «ячей- «ячейками» автомата. Приводятся общие методы анализа конечных автоматов. Большое внимание уделено синтезу конечных авто- автоматов. Излагаются общие методы синтеза, основанные на графических и аналитических способах задания операторов. Описываются различные практические прие- приемы синтеза, которые иллюстрируются большим числом примеров. Книга предназначена для студентов, аспирантов и паучных работников, специализирующихся в теории кибернетических систем, и инженеров, занимающихся разработкой цифровых автоматических устройств—вы- устройств—вычислительных и управляющих. Кобринский Натан Ефимович и Трахтенброт Борис Авраамович. Введение в теорию конечных автоматов. М. , Фиаматгиз, 1962 г. , 404 стр. с илл. Редактор Бирюков Б. В. Техн. редактор Мурашова Н. Я. Корректор Халанская А. Д. Сдано в набор 6/IX 1961 г. Подписано к печати 9/Ш 1962 г. Бумага 84хЮ81/зг- Физ. печ. л. 12. 625. Уоловн. печ. л. 20,71. Уч. -изд. л. 19,66. Тираж 15 000 экз. Т-00973. Цена книги 1 р. 18 к. Закав № 1246. Государственное издательство физико-математической литературы. Москва, В-71, Ленинский проспект, 15. Московская типография № 5 Мосгорсовнархоза Москва, Трехпрудный пер. , 9. ОГЛАВЛЕНИЕ Предисловие 5 Введение 9 Глава I. Элементы логики 23 § 1. Общие замечания 23 § 2. Элементы алгебры логики 27 § 3. Минимизация формул' алгебры логики 45 § 4. Разложение функций алгебры логики 59 § 5. Элементы логики предикатов 67 Глава II. Операторы. Логические сети 84 § 1. Общие замечания 84 § 2. Детерминированность операторов 89 § 3. Ограниченно-детерминированные операторы (опе- (операторы с конечным весом) 96 § 4. Элементы (элементарные автоматы) и схемы ... . 106 § 5. Логические сети 115 § 6. Реализуемость ограниченно-детерминированных опе- операторов. Задачи анализа и синтеза автоматов ... . 124 Глава III. Операторы физических элементов 130 § 1. Вводные замечания 130 § 2. Электронно-ламповые и полупроводниковые элементы 131 § 3.