ОПЕРАТОР АВТОМАТНЫЙ

— оператор, который реализуется в некотором инициальном автомате

О. а. Т является словарным оператором, перерабатывающим слова (конечные или бесконечные) во входном алфавите X в слова в выходном алфавите О. а. определяется рекуррентными соотношениями:

Он, очевидно, определен на мн-ве всех слов алфавита X, если автомат А является всюду определенным, и на некотором его подмножестве, если А — автомат, частичный.

Из определения О. а. видно, что он удовлетворяет следующим условиям: 1) если — слова одинаковой длины; 2) если Т определен на словах и у них начальные отрезки длины совпадают, т. е. то в также совпадают начальные отрезки длины ; 3) если Т определен на слове х, то он определен и на всяком начальном отрезке слова х.

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

Таким образом, изучение О. а. является, по существу, выяснением вопроса, какие вычисления можно осуществить на автоматах. Частными случаями О. а. являются константный оператор, перерабатывающий любую бесконечную последовательность входных букв в некоторую фиксированную последовательность выходных букв, и истинностный оператор, для которого существует отображение такое, что для любого t. Константные и истинностные операторы реализуются, соответственно, автоматами автономными и автоматами без памяти.

Введем ряд характеристик операторов. В дальнейшем под операторами будем понимать всюду определенные О. а. Оператор остаточным оператором оператора соответствующим входному слову , если связаны следующим образом. Для того, чтобы найти составляется слово и к нему применяется оператор Из полученного слова отбрасывается начальный отрезок, равный длине слова , и тогда остаток равен Операторы если найдется такое слово х длины к, что и различимыми, если найдется слово х такое, что

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

Спектром различимости Т наз. функцию равную (для каждого к) макс. числу попарно различимых остаточных операторов оператора Т. Спектром достижимости Т наз. ф-цию равную макс. числу слов длины к, таких, что соответствующие им остаточные операторы попарно различимы.

Для автоматов имеются родственные понятия — степень различимости и степень достижимости автомата А. Если автомат А реализует оператор Т, то для него Этот факт можно использовать, напр., для доказательства того, что данный О. а. не реализируем никаким автоматом данного класса автоматов.

Ряд других параметров операторов (и автоматов) — степень различимости, степень достижимости, степень восстановления и др. характеризуют поведение автоматов, и они используются при абстрактном синтезе автоматов, минимизации автоматов (см. Минимизация числа состояний автомата) и др. задачах абстрактной теории автоматов. См. также Алгебраическая теория автоматов.

Лит.: Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы. (Поведение и синтез). М., 1970 [библиогр. с. 389—395].

М. И. Кратко.