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

[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]

1.3. монета многократно подбрасывается н делается отметка при четных выпадениях цифры в последовательности цифр и при каждом втором (не обязательно подряд) выпадении герба {х - сторона монеты, г -отметка при броске).

1.4. две плоские фишки, каждая из которых имеет на одной стороне цифру 1, а на другой - цифру 2, подбрасываются одновременно много раз. после каждого подбрасывания подсчитывается сумма по модулю 2 чисел, выпавших при данном броске, чисел, выпавших в предыдущий раз, и суммы, подсчитанной в предыдущий раз (х - комбинация двух сторон фишек, z - сумма при броске).

1.5. грузовой лифт, обслуживающий трехэтажный магазин, имеет кнопку вызова на каждом этаже и работает по следующим правилам: если нажата одна кнопка, то лифт движется на этаж, на котором расположена данная кнопка; если нажаты одновременно две или три кнопки, то лифт движется на самый нижний из всех этажей, на которых нажаты кнопки. ни одна кнопка не может быть нажата во время движения лифта {х - этаж, на котором нажата кнопка, г - направление, в котором будет двигаться лифт, и число этажей, которые он при этом пройдет без остановки).

1.6. английский текст, состоящий из 26 букв алфавита и промежутков между буквами, просматривается с целью подсчета числа слов, которые рифмуются с «art» (х - буква или промежуток, z - увеличение общего счета).

1.7. на рис. 31.1 изображена схема л, на которую поступают сигналы от двух импульсных генераторов напряжения vi и vj-

1 1 »

-♦-0 выход

1 1 *

рис. 31.1.

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

1.8. на рис. 3 1.2 представлена модель нервной сети, где нервное волокно, обозначенное Vbx, соединено с источником, который




Рис. 3 1.2.

зачерненными маленькими кружками) и числом возбужденных «тормозящих входов» (показаны маленькими кружками) в момент v-i равна или превышает его «порог» (число, записанное внутри большого кружка) (х = VBx. г = Vbux)-

1.9. Работа вычислительного устройства, имеющего вход х и выход Z, определяется следующими уравнениями:

v = Jfv©iv i ©te/v-i.

av = Xv© te/v-i.

где каждая переменная принимает значения О или 1, знак © обозначает сложение по модулю 2 (х и г определены в условии задачи).

) Эта модель введена в работе фон Неймана (J. von N е u-m а п, Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components, «Automata Stu<lies», pp 43-98, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Дж. фон Нейман, Вероятностная логика и синтез надежных организмов из ненадежных элементов. В сборнике «Автоматы», под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956).

генерирует стимулы О или 1 в моменты времени ) Большой кружок представляет нейрон. Выход нейрона в момент-v возбужден (т. е. принимает значение 1) только в том случае, когда разность между числом его возбужденных «возбуждающих входов» (показаны



ГЛАВА 2

ТАБЛИЦЫ, ГРАФЫ И МАТРИЦЫ ПЕРЕХОДОВ

2.1. Введение

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

2.2. Таблица переходов

Характеристические функции и определяемые уравнениями (1.5) и (1.6), могут быть представлены в форме таблицы, известной под названием таблицы переходов. Таблица содержит перечень значений этих функций для всех возможных аргументов, т. е. для всех возможных упорядоченных пар (д:., s), где д:., принадлежит входному алфавиту X, а - множеству состояний 5. Образец таблицы

переходов для автомата с входным алфавитом {], 1,2.....Ьр]<

выходным алфавитом [t,, .....и множеством состояний {Oi, 02.....о„} представлен таблицей 2.1. Таблица

состоит из двух соседних подтаблиц г-подтаблицы и Зу-подтаблицы, которые определяют функции и Д соот-



[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.0011