En la teoría de los autómatas, un árbol es una forma particular de representar una estructura de árbol como secuencias de números naturales.
Por ejemplo, cada nodo del árbol es una palabra sobre un conjunto de números naturales (ℕ), lo que ayuda a que esta definición se utilice en la teoría de autómatas .
Un árbol es un conjunto T ⊆ ℕ * tal que si t . c ∈ T , con t ∈ ℕ * y c ∈ ℕ, luego t ∈ T y t . c 1 ∈ T para todo 0 ≤ c 1 < c . Los elementos de T se conocen como nodos , y la palabra vacía ε es el (único) de la raíz de T . Para cada t ∈ T , el elemento t. c ∈ T es un sucesor de t en la dirección c . El número de sucesores de t se denomina grado o aridad y se representa como d ( t ). Un nodo es una hoja si no tiene sucesores. Si cada nodo de un árbol tiene un número finito de sucesores, entonces se le llama árbol finito , de lo contrario infinitamente ramificado . Un camino π es un subconjunto de T tal que ε ∈ π y para cada t ∈ T , o t es una hoja o existe un c ∈ ℕ único tal que t . c ∈ π. Un camino puede ser un conjunto finito o infinito. Si todos los caminos de un árbol son finitos, entonces el árbol se llama finito, de lo contrario infinito. Un árbol se llama completamente infinito si todos sus caminos son infinitos. Dado un alfabeto Σ, un árbol etiquetado con Σ es un par ( T , V ), donde T es un árbol y V : T → Σ asigna cada nodo de T a un símbolo en Σ. Un árbol etiquetado define formalmente una estructura de árbol de términos de uso común. Un conjunto de árboles etiquetados se denomina lenguaje de árbol .
Un árbol se llama ordenado si hay un orden entre los sucesores de cada uno de sus nodos. La definición anterior de árbol sugiere naturalmente un orden entre los sucesores, que puede usarse para clasificar el árbol.
En el caso de alfabetos clasificados , se define una función adicional Ar : Σ → ℕ. Esta función asocia una aridad fija a cada símbolo del alfabeto. En este caso, cada t ∈ T tiene que satisfacer Ar ( V ( t )) = d ( t ). Los árboles que satisfacen esta propiedad se denominan árboles clasificados . Los árboles que no satisfacen (necesariamente) esa propiedad se denominan no clasificados .
Por ejemplo, la definición anterior se utiliza en la definición de un autómata de árbol infinito .
Ejemplo
Sea T = {0,1} * y Σ = { a , b }. Definimos una función de etiquetado V como sigue: el etiquetado para el nodo raíz es V (ε) = una y, para cada otro nodo t ∈ {0,1} * , los etiquetados para sus nodos sucesores son V ( t 0,0) = a y V ( t .1) = b . De la imagen se ve claramente que T forma un árbol binario (completamente) infinito.
Referencias
- Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (noviembre de 2008). "Preliminares". Técnicas y aplicaciones de Tree Automata (PDF) . Consultado el 11 de febrero de 2014 .