Cтраница 2
В зависимости от нашего выбора, получатся разные последовательности меток. [16]
Вершинами G ( С) служат состояния из 01 - Ребра определяются правилами функционирования R. Не нарушая общности, можно предположить, что С имеет только одно заключительное состояние 6, при достижении которого С останавливается. Каждому вычислению v, реализуемому преобразователем С в конкретной ситуации, можно сопоставить последовательность меток [ ( сигнал) ( оператор) ], - определяемых как снимаемый сигнал и применяемый оператор в соответствующие такты работы. Множество всех отметок вдоль пути из я0 к b задает множество всех принципиально возможных историй вычислений преобразователем. В силу теоремы 4.1 это множество R ( a0t b) - регулярно. На самом деле в реальных вычислениях преобразователя С не все слова из R ( a0, b) могут быть задействованы в качестве отметок историй вычислений, так как может случиться, что некоторые пути из R ( aQt b) никогда не реализуются. [17]