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

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