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

Словарная функция, характеризующая поведение автомата конечного. (Функция наз. словарной, если областью определения и областью значений ее являются множества слов или сверхслов.) Если А- какой-либо алфавит, то пусть обозначает множество всех слов, а — множество всех слов или множество всех сверхслов в алфавите А. Функция 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. Ю. И. Янов.