51. Ограниченно-детерминированные (автоматные) функции, способы их задания.

Определение.Количество классов эквивалентности вершин в бесконечном дереве детерминированной функции называется весом этой функции.

Определение.Детерминированная функция из классаF_k называется автоматной (или ограниченно-детерминированной) функцией, если она имеет конечный вес.

Автоматную функцию можно задать диаграммой Мура. Число вершин в ней равно весу автоматной функции, а сама диаграмма получается из конечного дерева с помощью отождествления в нем эквивалентных вершин.

Пример.Пусть требуется найти вес и построить диаграмму Мура автоматной функцииfF₂, выходная последовательность которой задана равенством у(t) =

Заметим, что в данном случае х(t), у(t){0, 1}.

На рисунке изображены четыре нижних яруса вершин бесконечного дерева, задающего функцию f.

Все дуги помечены парой чисел x(t), у(t). Кроме того, каждая вершина имеет числовую метку 0 или 1. Вершины с одинаковой меткой принадлежат одному классу эквивалентности, причем нулем помечен корень исходного дерева и все эквивалентные ему вершины. Таким образом, заданная функция имеет вес, равный двум. Следовательно, она является автоматной функцией и может быть задана конечным деревом. В нем должно быть ровно по одной внутренней вершине из каждого класса эквивалентности. Все остальные его вершины должны быть концевыми. Такое конечное дерево всегда позволит восстановить исходное бесконечное дерево. Конечное дерево, задающее автоматную функцию из примера 2, представлено на рисунке.

Теперь, чтобы получить диаграмму Мура для заданной автоматной функции, нужно в конечном дереве отождествить вершины с одинаковыми метками. В данном случае диаграмма Мура будет иметь две вершины и четыре дуги . Следовательно, существует конечный детерминированный автомат, способный вычислять заданную автоматную функцию. Начальным состоянием является 0.

Всякую автоматную функцию можно задать канонической системой уравнений вида

где функция Y – это функция выходов, Q – функция переходов, q(0) – начальное состояние автомата, вычисляющего данную автоматную функцию, а q(t – 1) и q(t) – состояния, в которых оказывается этот автомат соответственно в начале и в конце t-го такта. При этом предполагается, что множество состояний автомата V = {0, 1, 2, …, r – 1}. Функцию, рассмотренную в примере, можно задать канонической системой гдех(t), у(t), q(t){0, 1}.