Предсказание поведения автомата

Последовательность входных символов, в которой за символом ξ i ₁ следует ξ i ₂,... ξ i ₂, называется входной последовательностью и записывается так: ξ i ₁ ξ i ₂,... ξ i_l. Аналогично последовательность выходных символов ζj₁ζj₂... ζj _i

называется выходной последовательностью. Число символов в последовательности называется длиной последовательности.

Как следует из предположения о дискретности времени, возбуждения подаются на конечный автомат всегда в виде входных последовательностей, а реакции снимаются всегда в виде выходных последовательностей, причем входная последовательность длины l всегда вызывает выходную последовательность длины l. Состояние автомата М в момент

времени t ₁ называется начальным состоянием М. Так как t ₁ произвольно, то в качестве начального состояния автомата М обычно выбирается то состояние, в котором он находится перед началом работы.

Теорема 1.1. Пусть дан нетривиальный автомат М с характеристическими функциями f _z и f _s. Тогда реакцию автомата М, находящегося в любом начальном

состоянии σ_i0, на любую входную последовательность ξj₁ ξj₂,... ξj _l: (а) предсказать нельзя, если известны только f _z и f _s, (б) предсказать можно, если известны

f _z, f _s и σ_i0.

Доказательство. (а) Если М не тривиален, то из (1.8) следует, что имеется по крайней мере два состояния σ_u и σ _v и по крайней мере один входной символ ξ _h, такой, что

f_z(ξ_h,σ_u) ≠ f_z(ξ_h,σ_u). (1.26)

Тогда реакция М на последовательность ξ _h ξ j₂,... ξ j_l, при σ_io = σ_u отличается от реакции при σ_io = σ_v. Следовательно, если известны только f_z и f_s, то реакция по крайней мере

на одну из входных последовательностей не может быть предсказана, (б) Рассмотрим индуктивное предположение: если f_s и σ _io известны, то известно состояние σ _ik, в которое

придет М под воздействием входной последовательности ξ j ξ j₂,... ξ j_k. При k = 0 предположение очевидно. Если предположение справедливо для k, то σ _ik; известно, и тогда σi _k+1 может быть найдено благодаря знанию f_s:

σi_k₊₁= f_s (ξ j_k, σ i_k). (1.27)

Следовательно, по индукции, наше предположение справедливо для любого k ≥ 0. Если в дополнение к f_s и σ i_o известна функция f_z, то k -й выходной символ ζ h_k может быть определен по формуле

ξ h_k = f_z (ξ j_k, σ i_k). (1.28)

где σ i_k находится рекурсивно по формуле (1.27). Придавая k значения 1, 2,..., l, при известных f_z, f_g и σ i₀ можно предсказать выходную последовательность ζ h ₁ζ h ₂... ζ h_l для

любой входной последовательности ξ j₁ ξ j₂,... ξ j_i.

Теорема 1.1 показывает, что знание характеристических функций недостаточно для полного описания поведения автомата. С другой стороны, полное описание всегда возможно, когда, кроме этих функций, известно начальное состояние автомата. Этот факт, может быть легко продемонстрирован на примерах § 1.7, в которых определения систем не содержат сведений о начальных состояниях. В примере 1 реакцию на входную последовательность, содержащую символ «положительный стимул», предсказать нельзя. В примере 2 нельзя предсказать реакцию на входную последовательность, начинающуюся символом «π». В примере 3 нельзя предсказать реакцию на любую входную последовательность. Однако все реакции в этих примерах можно предсказать, если будет определено начальное состояние.

Эта ситуация похожа на ситуацию, встречающуюся при анализе линейных систем. Соотношения f_s и f_z в конечном автомате аналогичны уравнениям равновесия, характеризующим линейное устройство, а начальное состояние автомата аналогично начальному распределению энергии в устройстве. Реакция устройства на любое заданное воздействие может быть предсказана, когда известны и уравнения равновесия и начальное распределение энергии, но реакция не может быть предсказана, если не задано начальное распределение энергии.

Задачи

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

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

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

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

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

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

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

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

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

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

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

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