Strom (teorie automatů) - Tree (automata theory)

V teorii automatů, a strom je zvláštní způsob reprezentace a stromová struktura jako posloupnosti přirozených čísel.

Grafické znázornění označeného stromu popsaného v příkladu

Například každý uzel stromu je a slovo přes sadu přirozená čísla (ℕ), což umožňuje použití této definice v teorie automatů.

A strom je sada T ⊆ ℕ^* takové, že pokud t.C ∈ T, s t ∈ ℕ^* a C Then ℕ tedy t ∈ T a t.C₁ ∈ T pro všechny 0 ≤ C₁ < C. Prvky T jsou známé jako uzlya prázdné slovo ε je (jednoduché) vykořenit z T. Pro každého t ∈ Tprvek t.C ∈ T je nástupce z t v směr C. Počet nástupců t se nazývá jeho stupeň nebo arity, a reprezentován jako d(t). Uzel je a list pokud nemá žádné nástupce. Pokud má každý uzel stromu konečně mnoho následníků, pak se nazývá a konečně, jinak nekonečně se rozvětvuje strom. A cesta π je podmnožina T takové, že ε ∈ π a pro všechny t ∈ T, buď t je list nebo existuje jedinečný C ℕ ℕ takové t.C ∈ π. Cesta může být konečná nebo nekonečná množina. Pokud jsou všechny cesty stromu konečné, strom se nazývá konečný, jinak nekonečný. Strom se nazývá zcela nekonečný pokud jsou všechny jeho cesty nekonečné. Vzhledem k abeceda Σ, a Strom označený Σ je pár (T,PROTI), kde T je strom a PROTI: T → Σ mapuje každý uzel T na symbol v Σ. Označený strom formálně definuje běžně používaný období stromová struktura. Sada označených stromů se nazývá a jazyk stromu.

Strom se nazývá nařízeno pokud existuje pořadí mezi nástupci každého z jeho uzlů. Výše uvedená definice stromu přirozeně naznačuje pořadí mezi následníky, které lze použít k tomu, aby byl strom zařazen.

V případě seřazené abecedy, zvláštní funkce Ar: Je definováno Σ → ℕ. Tato funkce přidruží pevnou arititu ke každému symbolu abecedy. V tomto případě každý t ∈ T musí uspokojit Ar(PROTI(t)) = d(t). Stromy, které splňují tuto vlastnost, se nazývají zařadil stromy. Stromy, které tuto vlastnost (nutně) nesplňují, se nazývají nehodnocený.

Například výše uvedená definice se používá v definici automat nekonečných stromů.

Příklad

Nechat T = {0,1}^* a Σ = {A,b}. Definujeme funkci označování PROTI takto: označení kořenového uzlu je PROTI(ε) = A a pro každý další uzel t ∈ {0,1}^*, označení jeho následných uzlů jsou PROTI(t.0) = A a PROTI(t.1) = b. Z obrázku je zřejmé, že T tvoří (plně) nekonečný binární strom.

Reference

• Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (listopad 2008). "Přípravné zápasy". Techniky a aplikace stromových automatů (PDF). Citováno 11. února 2014.