Математическая энциклопедия - ограниченно-детерминированная функция

словарная функция, характеризующая поведение автомата конечного. (Функция наз. словарной, если областью определения и областью значений ее являются множества слов или сверхслов.)

Если Акакой-либо алфавит, то пусть обозначает множество всех слов, а множество всех слов или множество всех сверхслов в алфавите А. Функция 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.

Ю. И. Янов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985