.04 Детерминированные функции, ограниченно-детерминированные функции. Диаграммы Мура. Автоматы.

Построим информационное дерево для нашей функции.

И дело в том, что это дерево содержит бесконечно много неэквивалентных поддеревьев.

Действительно, рассмотрим, например, функцию, задающуюся деревом, растущим из вершины на чётном ярусе 2 :

Тогда функция, заданная этим поддеревом, примет значение единица через 2 яруса (на 4 ярусе исходного дерева).

В то время как, например, если рассмотреть функцию, задающуюся деревом, растущим из следующей вершины на чётном ярусе 4:

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

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

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