Детерминированный преобразователь
Cтраница 1
 |
Условный график движения управления преобразователя по структуре в зависимости от времени. Число пересечений горизонтальной линии d ограничено константой локальной ограниченности. [1] |
Детерминированные преобразователи - преобразователи Черча - Россера, так как они всегда имеют единственный результат. [2]
Такой детерминированный преобразователь Rt ( n) - это гис-терон. [3]
Таким образом, неидеальное реле является детерминированным преобразователем, определенным на всех непрерывных входах. Очевидны статичность и управляемость неидеального реле. [4]
Если над некоторой информационной областью 0 проблема эквивалентности для конечных детерминированных преобразователей неразрешима, то неразрешима и проблема проверки выполнимости свойства Черча-Россера. В самом деле, по двум детерминированным преобразователям Аг и Л2 легко построить недетерминированный преобразователь Л, который на первом шаге недетерминированно передает управление преобразователю Лх или Л2, а затем функционирует согласно правилам выбранного преобразователя. Преобразователь А - преобразователь Черча - Россера тогда и только тогда, когда Аг и А2 эквивалентны. Таким образом, для преобразователей над стандартной памятью или над целочисленной решеткой Z X Z проверка свойства Черча - Россера неразрешима, так как известно, что для детерминированных читающих преобразователей над этими структурами проблема эквивалентности неразрешима. [5]
Аналогичный подход может быть использован и в других конструкциях, в которых некоторый детерминированный преобразователь общего вида превращается в другой преобразователь путем введения ограничителей. [6]
Следствие 9.1. Любая булева комбинация локально-конечных свойств на свободной группе при ограниченных интерпретациях вычислима локально-конечным детерминированным преобразователем. [7]
Преобразователь называется детерминированным, если для каждой пары ах, а 6 01 х 6 X в множестве R имеется не более одного правила, имеющего ах своей левой частью. Детерминированный преобразователь всегда осуществляет только одно вычисление. [8]
 |
Дерево для выделения, недетерминированных ветвей регулярного выражения R у, J. [9] |
Отметим, что Величина г зависит только от вида регулярного выражения и, следовательно, Является константой, не зависящей от интерпретации вычислительной среды. При детерминизации регулярных выражений, соответствующих детерминированным преобразователям, происходит линейный рост чио-ла переменных. Однако само регулярное выражение может иметь экспоненциальный объем относительно числа состояний. [10]
Если над некоторой информационной областью 0 проблема эквивалентности для конечных детерминированных преобразователей неразрешима, то неразрешима и проблема проверки выполнимости свойства Черча-Россера. В самом деле, по двум детерминированным преобразователям Аг и Л2 легко построить недетерминированный преобразователь Л, который на первом шаге недетерминированно передает управление преобразователю Лх или Л2, а затем функционирует согласно правилам выбранного преобразователя. Преобразователь А - преобразователь Черча - Россера тогда и только тогда, когда Аг и А2 эквивалентны. Таким образом, для преобразователей над стандартной памятью или над целочисленной решеткой Z X Z проверка свойства Черча - Россера неразрешима, так как известно, что для детерминированных читающих преобразователей над этими структурами проблема эквивалентности неразрешима. [11]
Обозначим через u ( t), v ( t) ( t f0) Два допустимых входных сигнала на преобразователь W, находящийся при t / о в некотором фиксированном состоянии. Операторы (1.4), возникающие при описании физически реализуемых детерминированных преобразователей, называют вольтерровыми. [12]
Страницы: 1