Читать онлайн «Алгебраическая теория автоматов, языков и полугрупп»

АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ АВТОМАТОВ, ЯЗЫКОВ И ПОЛУГРУПП Под редакцией М. А. АРБИБА Перевод с английского Н. И. ОСЕТИНСКОГО Научный редактор Н. П. БУСЛЕНКО МОСКВА «СТАТИСТИКА» 1975 ALGEBRAIC THEORY OF MACHINES, LANGUAGES AND SEMIGROUPS Edited by Michael A. ARBIB ACADEMIC PRESS, NEW YORK AND LONDON 1968 6Ф7. 3 A79 A79 Алгебраическая теория автоматов, языков и полу- полугрупп. Под редакцией М. Арбиба. Пер. с англ. М. , «Ста- «Статистика», 1975. 335 с; с ил л. Монография посвящена рассмотрению математического аппарата количест- количественного и качественного анализа АСУ. Конечные автоматы благодаря их про- простой реализуемости на ЭВМ имеют значительные преимущества по сравнению с другими моделями. Авторы знакомят читателей с основными достижениями в этой области. Книга рассчитана иа разработчиков АСУ и цифровых средств вычисли- вычислительной техники, иа математиков, работающих в области системного матема- математического обеспечения и построения проблемио-ориейтироваииых алгоритмиче- алгоритмических языков, а также иа специалистов по системному анализу и моделирова- моделированию сложных объектов. ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Задачи системного анализа и исследования операций, разработки математического обеспечения АСУ, автоматизации проектирования и обработки больших массивов информации приводят к математиче- математическим моделям, среди которых существенное место занимают автоматы. Автоматы используются для формального описания реальных объек- объектов, которые при формализации могут быть адекватно представлены в виде дискретных систем. К ним относятся схемы устройств ЭВМ, реа- реализующие логические функции и арифметические операции, элементы памяти и каналы связи, осуществляющие запоминание и передачу текстов, процессы формирования исходных данных для принятия ре- решений, структуры коммуникационных сетей и т. д. Актуальностью изучения перечисленных и других подобных им объектов объясняется растущий интерес к теории автоматов, количественным и качественным методам их исследования, а также к алгоритмам моделирования на ЭВМ. Конечный автомат как математическая модель реального~объекта требует обычно двоякого рассмотрения. С одной стороны, он выступает как алфавитный преобразователь информации, реализующий соот- соответствующее алфавитное отображение, а с другой — как динамическая система, изменяющая свои состояния во времени под действием внеш- внешних сигналов и внутренних факторов. С первой точки зрения существенное значение имеют представле- ниесобытий, реализуемых данным конечным автоматом, процедуры абстрактного и структурного синтеза автоматов, минимизация числа его состояний и другие задачи, относящиеся к автоматическому пре- преобразованию информации. Эта часть теории автоматов выросла в серьезную научную дисциплину с большим числом работ, специфиче- специфическими методами и своеобразной проблематикой. В нашей стране упо- упомянутые вопросы получили существенное развитие благодаря трудам академика В.