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

Для функции с входным алфавитом и выходным алфавитом , заданной как:

найти её вес, нарисовать усечённое информационное дерево и построить диаграмму Мура.

Решение.

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

Теперь нам нужно понять, сколько в этом бесконечном информационном дереве неэквивалентных поддеревьев.

Ясно, что неэквивалентных поддеревьев будет всего 4. Это поддеревья вида

Следовательно, вес нашей функции равен 4.

2. Для того, чтобы построить усечённое информационное дерево, мы должны сначала выбрать и пометить числами 0 и 1, 2 и 3 четыре базовые вершины - корневую и любые три другие так, чтобы помеченные разными номерами вершины задавали неэквивалентные деревья. И из каждой вершины выпустить ребра. Получим такое усечённое дерево:

3. И, соответственно, диаграмма Мура получается, если мы в усечённом информационном дереве отождествим вершины с одинаковыми метками: