1.10] . ПРЕДСКАЗАНИЕ ПОВЕДЕНИЯ АВТОМАТА 29

ляет выходной сигнал >). Если мощность входного алфавита системы равна р, а мощность множества состояний5 равна л, то мощность 5 будет рп.

Система, соответствующая второй модели, определяемая уравнениями (1.21) и (1.23), может быть всегда представлена основной моделью, определяемой уравнениями вида (1.5) и (1.6), входящими в определение 1.1.

Это можно сделать, положив s= s y Тогда из равенства (1.21) получим:

Из определения и уравнения (1.23) получаем:

vi=<=/:(vCi)=/.(v)- (1-5)

Нетрудно видеть, что уравнения (1.24) и (1.25) выражают характеристические функции основной модели конечного автомата.

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

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

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

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

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

) Вторая модель соответствует автомату Мура. (Прим. перев.)

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

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

h\lj2 • • • Ji- предсказать нельзя, если известны только Д и (б) предсказать можно, если известны fz- fs и \-

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

Л(1д. о„)=Л(1д. oj. (1.26)

Тогда реакция М на последовательность • • при

a; = a„ отличается от реакции при ai = a„. Следовательно, если известны только и то реакция по крайней мере на одну из входных последовательностей не может быть предсказана, (б) Рассмотрим индуктивное предположение: если и известны, то известно состояние О;, в которое

придет М под воздействием входной последовательности Ijlj ... 1;. При k - 0 предположение очевидно. Если предположение справедливо для к, то о/ известно, и тогда Oi может быть найдено благодаря знанию Д:

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

где находится рекурсивно по формуле (1.27). Придавая k

значения 1, 2...../, при известных Д, и о можно

предсказать выходную последовательность CajCa • • Ц для любой входной последовательности ... Ij.

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

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

Задачи

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

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

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