б. Линия задержки

В качестве второго примера рассмотрим вновь (см. гл. V) воспроизведение медленной П-машины G с помощью быстрой машины , реализованной на быстрых элементах задержки.

Пусть требуется построить П-машину G, работающую в тактности, определяемой равномерным разбиением оси времени на интервалы по секунд. Множеством допустимых входных последовательностей для машины G пусть будет множество Е, содержащее все последовательности входных символов. Входной алфавит машины G содержит различных символов .

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

Но допустим, что мы такими элементами задержки не располагаем, а в нашем распоряжении имеются только «быстрые» -ичные элементы задержки, работающие в тактности, определяемой равномерным разбиением оси времени на интервалы по — (т. е. в q раз более быстрые), где .

Попробуем из имеющихся быстрых элементов задержки построить быструю П-машину S и подобрать такой закон преобразования тактности, чтобы эта быстрая машина воспроизводила заданную П-машину .

Уравнение быстрого элемента задержки (рис. 10.4) имеет вид

а уравнение требующегося нам медленного элемента задержки

Составим из q быстрых элементов задержки цепочку, как это изображено на рис. 10.5. Полученная цепочка описывается системой рекуррентных соотношений

Исключая из этой системы все кроме получаем для цепочки в целом уравнение

Уравнение (10.5) совпадает с уравнением (10.3) медленного элемента задержки; следовательно, цепочка из быстрых элементов равноценна одному медленному элементу.

Рис. 10.4.

Принимая это во внимание, построим П-машину S следующим образом. Предположив на время, что в нашем распоряжении имеются медленные элементы задержки (10.3), построим из них и мгновенно действующих логических преобразователей машину G по одному из описанных в гл. V способов.

Рис. 10.5.

Заменим затем в этой машине каждый медленный элемент задержки цепочкой из q быстрых задержек. В результате будет получена некоторая П-машина , работающая в быстрой тактности, а именно в той, в которой работают быстрые элементы задержки. Но если смотреть на машину S лишь в моменты с моментами , то машина S будет воспроизводить П-машину G, так как уравнение каждой цепочки быстрых задержек (10.4) для этих моментов совпадает с уравнением одного медленного элемента задержки.

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

Подсчет показывает, что при воспроизведении для каждого из состояний машины G имеется соответствующих ему состояний машины .

За множество допустимых входных последовательностей для машины S при воспроизведении может быть принято либо множество Е, либо множество R (не содержащее последовательностей с повторяющимися символами), либо множество М, содержащее все последовательности вида

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

«Часы» в рассмотренном случае представляют собой кольцевую счетную схему (т. е. автономный конечный автомат), собранную из быстрых элементов задержки, и выдающую сигнал наступления медленного такта по прошествии q быстрых тактов.

Обратим внимание, что в этом примере, так же как и в предыдущем, построение выполнено так удачно, что имеет место не только воспроизведение, но и изображение: машина 5 изображает машину G (как относительно множества Е, так и относительно любого иного множества). Соответствие состояний при изображении остается тем же.