ПРИМЕР 2. Автомат для проверки на четность

F	q0 q1
	0 1
	1 0

G	q0 q1
	q0 q1
	q0 q1

 

.

 

 

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

Или же, если мы знаем, что машина начала свое существование в состоянии 0, то можно сказать, было ли общее число единиц, поступивших в машину за все прошедшее время четным или нечетным.

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

Когда мы имеем дело с большим числом состояний вместо таблиц переходов удобнее использовать диаграммы состояний ( диаграммы переходов).

Диаграммы состояний для рассмотренных выше примеров приведены на рис.

Рис. Запоминающий автомат Рис. Автомат для проверки

на четность.

 

Правила работы с диаграммами следующие: состояние всегда изображается(представляется) шестиугольником. Стрелки обозначают переходы из одного состояния в другое. Символ входного состояния указывается на хвосте стрелки, выходящей из состояния. Каждая стрелка показывает, что происходит , если дано состояние и входной сигнал. Острие стрелки указывает на следующее состояние, определяемое значением функции G. Символ , помещенный в разрыв стрелки, определяет значение выходного сигнала, который появится в соответствии со значением функции F.