Перед доказательством следующей теоремы введем еще одно определение.

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

где  ,  ,

где – предпериод, а – период.

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

Теорема 1. Последовательность выходных сигналов коллектива из двух автоматов на целочисленной прямой, является периодической.

Доказательство: Передвигаясь на целочисленной прямой, 2 автомата и  могут оказаться на расстоянии не большем

а) 0 раз

б) конечное число раз

в) бесконечное число раз

Рассмотрим каждый из трёх случаев на произвольном коллективе из двух автоматов и  . Положим, что число состояниний первого автомата , а число состояний второго автомата .

Рассмотрим случай а), когда автоматы и  , в каждый момент времени ,

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

 

Так как состояний у автоматов и  - конечное число, то при , не позднее  чем через n тактов, а при – не позднее чем через

тактов, найдется такт с номером такой, что пара состояний и певого и второго автоматов соответственно, будут теми же самыми, что и в некоторый момент  .  Т. е. будет выполняться следующая система уравнений:

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

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8