Ограниченно-детерминированная Функция

- словарная функция, характеризующая поведение автомата конечного. (Функция наз. Словарной, если областью определения и областью значений ее являются множества слов или сверхслов.) Если А- какой-либо алфавит, то пусть обозначает множество всех слов, а - множество всех слов или множество всех сверхслов в алфавите А. Функция f, отображающая в , где Аи В- произвольные конечные алфавиты, наз. Детерминированной функцией, если выполняются следующие два условия. 1) для любого из длина равна длине аи 2)если- слово длины lигде , то значения и имеют одинаковые начала длины l. Если детерминированная функция f определена на множестве всех сверхслов в алфавите А, то в силу условий 1) и 2) она однозначно распространяется на множество .

Для произвольного слова длины lзначение f(a) совпадает с началом длины lзначения , где - произвольное сверхслово в алфавите А. Таким образом, всякая детерминированная функция f удовлетворяет условию. 3) для любого слова из и любого из справедливо равенство где - нек-рая детерминированная функция на множестве , однозначно определяемая словом . Функция fa , наз. Остаточной функцией для f. Из условия 3) следует, что всякая детерминированная функция f определяет на множестве отношение эквивалентности тогда и только тогда, когда . Ранг этого отношения, или, что то же, максимальное число попарно различных остаточных функций, наз. Весом детерминированной функции f. Если вес детерминированной функции конечен, то она наз.

Ограниченно-детерминированной функцией. Это понятие распространяется и на функции от тпеременных, где если наборы из тслов одинаковой длины (или сверхслов) в алфавитах соответственно рассматривать как слова (сверхслова) в алфавите являющемся декартовым произведением алфавитов . Таким же образом можно рассматривать О.-д. Ф. С несколькими выходами, т. Е. Значениями к-рых являются наборы из кслов или сверхслов соответственно в алфавитах Класс всех О.-д. Ф. Совпадает с классом функций, вычислимых конечными автоматами. Поэтому для задания О.-д. Ф. Могут быть использованы те же средства, что и для задания конечных автоматов, напр, канонич. Уравнения (см. Автомат конечный, Автоматов способы задания). Отсюда следует, в частности, что класс О.-д.

Ф. С совпадающими алфавитами замкнут относительно суперпозиций. Минимальный (по числу состояний) автомат вычисляющий О.-д. Ф. F веса т, содержит псостояний и может быть построен следующим образом. Пусть - произвольные представители всех классов эквивалентности отношения R. Каждому классу ставится в соответствие нек-рое состояние автомата . Функция переходов j и функция выходов определяются следующими условиями. Если где состояние соответствует классу В качестве начального берется состояние, соответствующее классу R(е), где е - пустое слово. Лит.:[1] Кудрявцев В. Б., Лекции по теории конечных автоматов, М., 1976. [2] Яблонский С. В., Введение в дискретную математику, М., 1979. Ю. И. Янов..