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

- словарная функция, характеризующая поведение автомата конечного. (Функция наз. словарной, если областью определения и областью значений ее являются множества слов или сверхслов.) Если А- какой-либо алфавит, то пусть [img: http://localhost:8080/file/031604-137.jpg] обозначает множество всех слов, а [img: http://localhost:8080/file/031604-138.jpg] - множество всех слов или множество всех сверхслов в алфавите А. Функция f, отображающая [img: http://localhost:8080/file/031604-139.jpg] в [img: http://localhost:8080/file/031604-140.jpg], где Аи В- произвольные конечные алфавиты, наз. детерминированной функцией, если выполняются следующие два условия: 1) для любого [img: http://localhost:8080/file/031604-141.jpg] из [img: http://localhost:8080/file/031604-142.jpg] длина [img: http://localhost:8080/file/031604-143.jpg] равна длине аи 2)если- [img: http://localhost:8080/file/031604-144.jpg] слово длины lигде [img: http://localhost:8080/file/031604-145.jpg] [img: http://localhost:8080/file/031604-146.jpg], то значения [img: http://localhost:8080/file/031604-147.jpg] и [img: http://localhost:8080/file/031604-148.jpg] имеют одинаковые начала длины l. Если детерминированная функция f определена на множестве [img: http://localhost:8080/file/031604-149.jpg] всех сверхслов в алфавите А, то в силу условий 1) и 2) она однозначно распространяется на множество [img: http://localhost:8080/file/031604-150.jpg]: для произвольного слова [img: http://localhost:8080/file/031604-151.jpg] длины lзначение f(a) совпадает с началом длины lзначения [img: http://localhost:8080/file/031604-152.jpg], где [img: http://localhost:8080/file/031604-153.jpg] - произвольное сверхслово в алфавите А. Таким образом, всякая детерминированная функция f удовлетворяет условию: 3) для любого слова [img: http://localhost:8080/file/031604-154.jpg] из [img: http://localhost:8080/file/031604-155.jpg] и любого [img: http://localhost:8080/file/031604-156.jpg] из [img: http://localhost:8080/file/031604-157.jpg] справедливо равенство [img: http://localhost:8080/file/031604-158.jpg] где [img: http://localhost:8080/file/031604-159.jpg] - нек-рая детерминированная функция на множестве [img: http://localhost:8080/file/031604-160.jpg], однозначно определяемая словом [img: http://localhost:8080/file/031604-161.jpg]. Функция fa, наз. остаточной функцией для f. Из условия 3) следует, что всякая детерминированная функция f определяет на множестве [img: http://localhost:8080/file/031604-162.jpg] отношение эквивалентности [img: http://localhost:8080/file/031604-163.jpg] тогда и только тогда, когда [img: http://localhost:8080/file/031604-164.jpg]. Ранг этого отношения, или, что то же, максимальное число попарно различных остаточных функций, наз. весом детерминированной функции f. Если вес детерминированной функции конечен, то она наз. ограниченно-детерминированной функцией. Это понятие распространяется и на функции от тпеременных, где [img: http://localhost:8080/file/031604-165.jpg] если наборы из тслов одинаковой длины (или сверхслов) в алфавитах [img: http://localhost:8080/file/031604-166.jpg] соответственно рассматривать как слова (сверхслова) в алфавите [img: http://localhost:8080/file/031604-167.jpg] являющемся декартовым произведением алфавитов [img: http://localhost:8080/file/031604-168.jpg]. Таким же образом можно рассматривать О.-д. ф. с несколькими выходами, т. е. значениями к-рых являются наборы из кслов или сверхслов соответственно в алфавитах [img: http://localhost:8080/file/031604-169.jpg] Класс всех О.-д. ф. совпадает с классом функций, вычислимых конечными автоматами. Поэтому для задания О.-д. ф. могут быть использованы те же средства, что и для задания конечных автоматов, напр, канонич. уравнения (см. Автомат конечный, Автоматов способы задания). Отсюда следует, в частности, что класс О.-д. ф. с совпадающими алфавитами [img: http://localhost:8080/file/031604-170.jpg] замкнут относительно суперпозиций. Минимальный (по числу состояний) автомат [img: http://localhost:8080/file/031604-171.jpg] вычисляющий О.-д. ф. f веса т, содержит псостояний и может быть построен следующим образом. Пусть [img: http://localhost:8080/file/031604-172.jpg] - произвольные представители всех классов эквивалентности отношения R. Каждому классу [img: http://localhost:8080/file/031604-173.jpg] ставится в соответствие нек-рое состояние [img: http://localhost:8080/file/031604-174.jpg] автомата [img: http://localhost:8080/file/031604-175.jpg]. Функция переходов j и функция выходов [img: http://localhost:8080/file/031604-176.jpg] определяются следующими условиями: если [img: http://localhost:8080/file/031604-177.jpg] где состояние [img: http://localhost:8080/file/031604-178.jpg] соответствует классу [img: http://localhost:8080/file/031604-179.jpg] В качестве начального берется состояние, соответствующее классу R(е), где е - пустое слово.