Главная  Кибернетика 

[0] [ 1 ] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

(например, нервной клетке, математическому алгоритму, электронной вычислительной машине), которая поддается моделированию с помощью конечного автомата. Опущено также общее рассмотрение модулярных последователь постных машин (хотя о линейных двоичных машинах говорится подробно) из-за требующейся для такого рассмотрения обширной математической подготовки. Наконец, было решено исключить из рассмотрения машины Тьюринга и цепи Маркова, так как, хотя эти темы и тесно связаны с предметом теории конечных автоматов, они составляют отдельные и независимые математические дисциплины, которые в достаточной степени освещены в других пособиях.

Основная часть этой книги первоначально была написана как конспект курса по конечным автоматам, прочитанного в Калифорнийском университете в Беркли в течение весеннего семестра 1961 года. Хотя курс был прочитан на электротехническом факультете, материал предназначается не специально инженеру-электрику, а любому специалисту - будь он экономистом или транспортным инженером, математиком или проектировщиком схем,-интересы которого лежат в сфере теории систем. В то же время материал этой книги особо рекомендуется инженерам по электронике и математикам-прикладникам, специализирующимся в области управления, связи или цифровых вычислений. Студентам, которые собираются стать специалистами по вычислительной технике и ее приложениям, материал может дать полезную подготовку к курсам по логическому синтезу и программированию.

Книга не предполагает какой-либо глубокой математической подготовки у читателя, хотя «математическая зрелость», добытая путем предварительной учебы, несомненно,-полезна. Уровень изложения соответствует уровню аспирантов или студентов, начинающих дипломную работу. Очень желательно, чтобы читатель потрудился над задачами, которыми



сопровождается каждая глава, так как эти задачи служат не только для иллюстрации, но и для пополнения текстового материала. Однако в принципе текст сам по себе полностью независим от задач.

Автор глубоко обязан доктору Л. А. Заде из Калифорнийского университета, чей семинар по системам с дискретными состояниями и автоматам (проводившийся в Беркли весной 1960 года) внес большой вклад в точку зрения, принятую в этой книге, а также в ее содержание. Автор также выражает благодарность доктору Д. А. Хаффмену из Массачу-сетского технологического института за несколько поощряющих бесед во время его визита в Беркли весной 1961 года.

Артур Гилл



ГЛАВА 1 ОСНОВНАЯ МОДЕЛЬ

1.1. Введение

Подобно другим теориям, развитие которых побуждается нуждами, науки и техники, теория конечных автоматов имеет дело с математическими моделями, предназначенными для приближенного отображения физических или абстрактных явлений. Значение этой теории состоит в том, что применение ее моделей не ограничивается какой-либо частной областью, а возможно непосредственно для решения проблем практически в любой области исследований от психологии до административного управления и от связи до лингвистики. Идеи и техника теории конечных автоматов используются для решения таких, казалось бы не связанных, проблем, как исследование деятельности нервной системы человека, анализ английского синтаксиса и проектирование электронных вычислительных машин. В эпоху, когда темпы развития науки сильно зависят от межотраслевого кооперирования, унифицированный характер этой теории представляет несомненную ценность.

В этой главе будет введена так называемая «основная модель» конечного автомата, будут детально обсуждены предположения, лежащие в основе этой модели, и будет показано, как эта модель может быть использована для решения проблем из самых различных областей.

1.2. Многополюсный черный ящик

Большинство проблем, встречающихся в науке и технике, можно разбить на следующие две категории: задачи анализа, которые состоят в предсказании поведения определенной заданной системы, и задачи синтеза, состоящие в построении системы по заданному поведению. В этой книге предпочтение будет оказано скорее задачам анализа, чем синтеза. Как



[0] [ 1 ] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.001