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

Последовательность входных символов, в которой за символом следует называется входной последовательностью и записывается так: . Аналогично последовательность выходных символов называется выходной последовательностью. Число символов в последовательности называется длиной последовательности.

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

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

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

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

Тогда реакция М на последовательность при отличается от реакции при . Следовательно, если известны только , то реакция по крайней мере на одну из входных последовательностей не может быть предсказана. (б) Рассмотрим индуктивное предположение: если известны, то известно состояние в которое придет М под воздействием входной последовательности . При предположение очевидно. Если предположение справедливо для k, то известно, и тогда может быть найдено благодаря знанию

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

где находится рекурсивно по формуле (1.27). Придавая значения при известных можно предсказать выходную последовательность для любой входной последовательности

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

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