Дерево (теория автоматов) - Tree (automata theory)

В теории автоматов дерево - это особый способ представления древовидной структуры в виде последовательностей натуральных чисел.

Графическая иллюстрация размеченного дерева, описанного в примере

Например, каждый узел дерева представляет собой слово над множеством натуральных чисел (ℕ), что помогает использовать это определение в теории автоматов .

Дерево представляет собой набор Т ⊆ ℕ ^* такое , что если т . c ∈ T , где t ∈ ℕ ^* и c ∈ ℕ, то t ∈ T и t . c ₁ ∈ T для всех 0 ≤ c ₁ < c . Элементы T известны как узлы , а пустое слово ε есть (один) корень из T . Для любого t ∈ T элемент t . с ∈ T является преемником из т в направлении с . Число последователей t называется его степенью или арностью и обозначается как d ( t ). Узел является листом, если у него нет наследников. Если каждый узел дерева имеет конечное число последователей, то он называется конечным , иначе - бесконечно ветвящимся деревом. Путь л представляет собой подмножество Т такое , что ε ∈ π и для каждого т ∈ T , либо т представляет собой лист или существует единственное с ∈ ℕ таким образом, что т . c ∈ π. Путь может быть конечным или бесконечным множеством. Если все пути дерева конечны, то дерево называется конечным, в противном случае - бесконечным. Дерево называется полностью бесконечным, если все его пути бесконечны. Для алфавита Σ Σ-помеченное дерево - это пара ( T , V ), где T - дерево, а V : T → Σ отображает каждый узел T в символ в Σ. Помеченное дерево формально определяет обычно используемый термин древовидная структура. Набор помеченных деревьев называется языком деревьев .

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

В случае ранжированных алфавитов определяется дополнительная функция Ar : Σ → ℕ. Эта функция связывает фиксированную арность с каждым символом алфавита. В этом случае для каждого t ∈ T должно выполняться условие Ar ( V ( t )) = d ( t ). Деревья, удовлетворяющие этому свойству, называются ранжированными деревьями. Деревья, которые (не обязательно) удовлетворяют этому свойству, называются неранжированными .

Например, приведенное выше определение используется в определении автомата с бесконечным деревом .

пример

Пусть T = {0,1} ^* и Σ = { a , b }. Мы определяем функцию разметки V следующим образом: разметка для корневого узла равна V (ε) = a, а для каждого другого узла t ∈ {0,1} ^* метки для его последующих узлов равны V ( t .0) = a и V ( t .1) = b . Из рисунка видно, что T образует (полностью) бесконечное двоичное дерево.

Ссылки

• Комон, Юбер; Дауше, Макс; Гиллерон, Реми; Жакемар, Флоран; Лужие, Денис; Лёдинг, Кристоф; Тисон, Софи; Томмази, Марк (ноябрь 2008 г.). «Отборочные». Методы и приложения древовидных автоматов (PDF) . Проверено 11 февраля 2014 .