Главная > Методы обработки данных > Введение в теорию конечных автоматов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Задачи

1.1. Опишите три системы, которые могут быть представлены конечными автоматами. Перечислите входной алфавит, выходной алфавит и множество состояний и дайте обоснование вашего выбора множества состояний.

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

1.2. Двоичные цифры 0 и 1 подаются на устройство, которое считает по модулю 3 накопленное число единиц — входные цифры, z — накопленное число).

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

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

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

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

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

Рис. 3 1.1.

Каждый генератор генерирует положительный или отрицательный импульс с периодом 1 микросекунда. Элемент d вызывает задержку импульса на 1 микросекунду. Схема N выдает положительный импульс, когда оба поступающих на ее входы импульса положительны, и выдает отрицательный импульс во всех остальных случаях — комбинация значений входных напряжений, — значение выходного напряжения).

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

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

Рис. 3.1.2.

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление