4.3. Ограниченно детерминированные функции. Информационное дерево

Пусть – множество. Каждую бесконечную последовательность где будем называть сверхсловом. Обозначим через множество всех таких сверхслов. Пусть – два конечных множества, их мы будем называть алфавитами. Рассмотрим отображение Это отображение можно интерпретировать как воображаемое устройство, перерабатывающее сверхслова в алфавите в сверхслова в алфавите (см. рисунок 4.13).

В ыясним, каким условиям должна удовлетворять функция чтобы она могла быть реализована некоторым автоматическим устройством. Если это устройство работает в дискретном режиме времени, получая в момент времени символ и выдавая символ то должен быть выполнен закон причинности (“причина предшествует следствию”); в нашем случае это означает, что может зависеть от но не должно зависеть от Исходя из этого, сформулируем определение детерминированной функции.

Функция называется детерминированной (или д-функцией), если выполнено условие: для любого и для любых сверхслов если и то

Итак, детерминированная функция характеризуется тем, что является функцией лишь от

С множеством можно связать некоторое бесконечное дерево Опишем его построение. Пусть Возьмём любую точку и назовём её корнем дерева. Из корня выпустим рёбер, концы которых назовём вершинами первого яруса. Из каждой вершины первого яруса выпустим рёбер, которые назовём вершинами второго яруса. И т.д. (см. рис. 4.14).

Ветви дерева (бесконечные) соответствуют сверхсловам причём это соответствие взаимно однозначное. Будем считать, что рёбра, соответствующие буквам алфавита идут слева направо (т.е. крайнее левое ребро соответствует букве следующее – букве крайнее правое – букве На рисунке изображено дерево, построенное для трёхбуквенного алфавита Ветвь дерева, отмеченная жирной линией, соответствует сверхслову а ветвь, отмеченная пунктирной линией, – сверхслову

Пусть дана детерминированная функция Построим дерево соответствующее множеству и пометим его рёбра буквами алфавита как будет показано ниже. Рассмотрим произвольное сверхслово Пусть Рассмотрим ветвь дерева соответствующую сверхслову и пометим рёбра этой ветви символами Так поступим с каждой ветвью. Если у двух сверхслов и совпадут первые букв: то ввиду детерминированности функции у сверхслов и также будут совпадать первые букв. Следовательно, в процессе расстановки пометок на рёбрах мы не получим противоречия (т.е. каждое ребро дерева получит ровно одну пометку). Дерево рёбра которого помечены вышеописанным способом, назовём информационным деревом, соответствующим функции и обозначим его Наоборот, если дано дерево для то, пометив его рёбра буквами из произвольным образом, мы получим информационное дерево, соответствующее некоторой функции Очевидно, соответствие между информационными деревьями и детерминированными функциями является взаимно однозначным.

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

П усть дано информационное дерево соответствующее детерминированной функции Для любой вершины этого дерева пусть обозначает поддерево, корнем которого является вершина (оно состоит из вершины и всех вершин и рёбер, идущих “после” вместе с пометками на этих рёбрах) (см. рис. 4.15).

Введём отношение эквивалентности ~ на множестве вершин дерева полагая если у деревьев и соответствующие друг другу рёбра имеют одинаковые пометки. Детерминированная функция называется ограниченно детерминированной (или о.д.-функцией), если множество вершин информационного дерева разбивается на конечное число ~-классов.

П ример. Пусть функция определяется правилом (здесь + обозначает сложение по модулю 2). Изобразим информационное дерево (см. рис. 4.16).

М ожно заметить (и это легко проверяется), что все вершины вида

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

Следующее утверждение устанавливает связь между понятиями о.д.-функции и конечного автомата.

Теорема. Ограниченно детерминированные функции и только они являются автоматными, т.е. реализуются некоторым конечным автоматом. При этом является входным алфавитом автомата, а – выходным.

П оясним, как строится диаграмма Мура автомата, реализующего данную о.д.-функцию В нашем случае множество вершин информационного дерева имеет лишь конечное число ~-классов. Обозначим классы через и пометим этими буквами вершины дерева причём корень пометим символом Нарисуем кружочков (см. рис. 4.17).

Если в информационном дереве есть ребро , то соединим кружочки и стрелкой, помеченной парой где – буква алфавита соответствующая данному ребру информационного дерева. Мы получим (см. рис. 4.18):

П роделав такую процедуру со всеми возможными парами кружочков, мы получим диаграмму Мура некоторого конечного автомата. Ясно, что этот автомат реализует функцию

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

Замечание. Всякая детерминированная, но не ограниченно детерминированная функция может быть реализована с помощью “бесконечного автомата”, т.е. “автомата” с бесконечным множеством состояний

П ример. Пусть и – функция, определяемая равенством (эта функция была рассмотрена перед теоремой). Ранее мы видели, что функция в этом примере является ограниченно детерминированной, так как дерево имеет два класса эквивалентности. Обозначив эти классы через и получим диаграмму Мура автомата, реализующего эту функцию (см. рис. 4.19).

“Физический смысл” состояний заключается в следующем. Нахождение автомата в состоянии означает, что предыдущая сумма была равна 0, и потому состояние будет в случае, когда в этом случае Таким образом автомат “запоминает” необходимую для дальнейшего “предысторию” последовательности

Упражнение 9. Выяснить, какие из следующих функций являются детерминированными:

а)

б)

в)

г)

Решение. а) Функция является детерминированной, так как при не зависит от

б) Функция не является детерминированной, так как зависит от которое неизвестно в момент времени

в) Функция детерминированная, так как – не зависит от

г) Функция детерминированной не является, так как выходная последовательность определится только тогда, когда будут известны для всех Другое объяснение:

а это противоречит определению детерминированности.

Упражнение 10. Выяснить, какие из следующих функций являются ограниченно детерминированными:

а)

б) ( );

в)

Р ешение. а) Построим информационное дерево соответствующее функции (рис. 4.20):

У нас имеются вершины двух видов (см. рис. 4.21а и рис. 4.21б).

Очевидно, вершины вида а) составляют один класс эквивалентности, а вершины вида б) – другой. Так как получилось конечное число классов (два класса), то функция ограниченно детерминирована.

б) Информационное дерево данной функции имеет вид (рис. 4.22)

М ножество вершин разбивается на 4 класса эквивалентности, поэтому функция ограниченно детерминирована.

в ) Информационное дерево данной функции имеет вид (рис. 4.23)

Докажем, что вершины не эквивалентны друг другу. Действительно, дерево с корнем имеет ветвь, изображённую на рис. 4.24.

Ясно, что количество нулей перед первой единицей на ветви, идущей из на 2 больше, чем на ветви, идущей из Значит, деревья отличаются друг от друга. Следовательно, имеется бесконечно много классов эквивалентности вершин дерева Это означает, что функция не является ограниченно детерминированной (хотя является, разумеется, детерминированной).

Можно дать интуитивное объяснение тому факту, что функция данного примера не является ограниченно детерминированной. Действительно, для того, чтобы сформировать надо помнить и с ростом объём информации, которую нужно помнить, растёт неограниченно. Поэтому функция не может быть реализована автоматом с конечным числом состояний.

Этот пример позволит сделать ещё одно важное замечание.

Замечание. Ранее было отмечено, что конечный автомат переводит всякую периодическую последовательность в периодическую. Оказывается, что обратное утверждение неверно. Существует детерминированная функция, переводящая всякую периодическую последовательность в периодическую, но не являющаяся ограниченно детерминированной. Примером может служить функция из предыдущей задачи:

У пражнение 11. На рисунке 25 изображён фрагмент информационного дерева некоторой о.д.-функции. Каково наименьшее возможное число классов эквивалентности вершин этого дерева?

Решение. Понятно, что и а также и лежат в разных ~-классах. Кроме того, рассматривая ветви длины 3, можно заметить, что Рассмотрение ветвей длины 2 показывает, что Возможно попадание в один класс эквивалентности вершин и а также и (или и Таким образом, наименьшее число классов эквивалентности равно 4. Один из вариантов разбиения на классы эквивалентности следующий: