Построение диаграмм Мура для ограниченно детерминированных функций

A = B = E₂ = {0, 1}

Каждому ребру припишем 0 или 1 по следующему правилу: 0 – левое ребро 1 – правое ребро

Для любого слова a можно найти только одни ориентированный путь, идущий из корня, двигаясь по которому можно прочитать слово a.

Например, пусть p = e₁e₂…e_n, j(p) = j(e₁)…j(e_n)

y(e_i)- отображение, задающее значения функции.

y(p) = f(a), где f – некоторая функция, связанная с информационным деревом.

Пример: a = 110,

1) |f(a)| = 3 = |a| 2) f(ab) = f(a)fa(b)

Þ f - детерминируема

Определение. Функция может быть представлена информационным деревом, тогда и только тогда, когда она детерминируема.

T(V_i) ~ f(a) – поддерево, растущее ниже.

Определение. Вершины V₁ и V₂ называются эквивалентными, если остаточные функции, соответствующие деревьям T(V₁) и T(V₂) одинаковые. Если собрать все эквивалентные вершины в класс, то каждый класс будет соответствовать какой-либо остаточной функции. Таких классов будет столько, сколько остаточных функций. Таким образом, функция является ограниченно детерминируемой тогда и только тогда, когда число классов эквивалентных вершин в информационном дереве конечно.

Пример:

f(x₁, x₂, …, x_n, …) º [по определению] º f(x) = x₁, x₁ Å x₂, x₁ Å x₂ Å x₃, x₃ Å x₄ Å x₅, … - детерминируема, так как любое y_i зависит от x₁, …, x_i-1

1)

f₀(x) = x₁, x₁ Å x₂, x₁ Å x₂ Å x₃, … = f(x)

f₁(x) = 1 Å x₁, 1 Å x₁ Å x₂ Å x₃, …

2)

f₁₀(x) = 1 Å x₁, x₁ Å x₂, x₁ Å x₂ Å x₃, …

f₁₁(x) = x₁, 1 Å x₁ Å x₂, x₁ Å x₂ Å x₃, …

Далее аналогично

3) f₀₀₀(x) = x₁, x₁ Å x₂, x₁ Å x₂ Å x₃, …

f₁₀₁(x) = 1 Å x₁, 1 Å x₁ Å x₂, x₁ Å x₂ Å x₃, …

f₁₁₀(x) = 1 Å x₁, x₁ Å x₂, x₁ Å x₂ Å x₃, …

f₁₁₁(x) = x₁, 1 Å x₁ Å x₂, x₁ Å x₂ Å x₃, …

(Лекция 14)

f = f₀ f₁₀

f₁ f₁₁

Теперь строим диаграмму Мура. Для этого склеим все одинаковые вершины.