§ 10.2. Примеры изображения и воспроизведения

а. Триггер

В качестве первого примера приведем триггер, описанный в гл. V.

Таблица 10.4

Таблица 10.5

Рассмотрим сначала автомат П — Н, основная таблица которого имеет вид табл. 10.4, при условии, что автомат получает входные последовательности из множества R, содержащего все последовательности, не имеющие следующих подряд друг за другом одинаковых символов.

Прочерки в таблице означают, что в соответствующие клетки при работе автомата мы никогда не попадем, и эти клетки можно заполнить произвольно.

Заполним как-либо пустые клетки табл. 10.4, например так, как показано в табл. 10.5.

Диаграмма состояний этого автомата будет тогда иметь вид рис. 10.2. Будем наблюдать теперь автомат (рис. 10.2) лишь в моменты , когда состояние входа изменяется с на , и выясним, какую машину G изображает относительно R этот автомат.

Рис. 10.2.

Прежде всего, можно определить множество допустимых входных последовательностей машины G. Так как мы наблюдали наш автомат лишь в те моменты, когда , то, естественно, множество будет содержать лишь последовательности единиц. Иначе это означает, что машина G будет автономной последовательностной машиной.

Рассмотрев различные варианты работы автомата рис. 10.2, легко прийти к выводу, что П-машина G (точнее, одна из многих возможных машин G), которую изображает наш автомат, обладает диаграммой состояний рис. 10.3. Легко видеть, что полученная медленная машина G является триггером (см. § 5.2). Соответствие состояний исходного автомата S и машины G (триггера) легко проследить; оно определено табл. 10.6.

Рис. 10.3.

Таблица 10.6

Отметим, что если бы заполнение пустых клеток таблицы 10.4 провести иначе, а именно так, как это сделано в табл. 10.7, то соответствие состояний исходного автомата и изображаемого им триггера G было бы такое, как показано в табл. 10.8.

Таблица 10.7

Таблица 10.8

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

Отметим также, что в рассмотренном примере исходный автомат S не только изображает относительно R триггер G, но и воспроизводит его относительно множества , содержащего входные последовательности, составленные лишь из единиц. За множество допустимых входных последовательностей исходного автомата при воспроизведении можно принять либо множество Е, включающее все последовательности нулей и единиц, либо множество , либо вообще какое-нибудь множество, включающее .