Un autómata de árbol es un tipo de máquina de estados . Los autómatas de árbol trabajan con estructuras de árbol , en lugar de con las cadenas de las máquinas de estados más convencionales.
El siguiente artículo trata sobre los autómatas de árboles ramificados, que corresponden a los lenguajes regulares de árboles .
Al igual que los autómatas clásicos, los autómatas de árboles finitos (FTA) pueden ser autómatas deterministas o no. Según cómo procese el autómata el árbol de entrada, los autómatas de árboles finitos pueden ser de dos tipos: (a) de abajo hacia arriba, (b) de arriba hacia abajo. Este es un tema importante, ya que, aunque los autómatas de árboles de abajo hacia abajo no deterministas (ND) y los autómatas de árboles de abajo hacia arriba ND son equivalentes en poder expresivo, los autómatas de árboles de arriba hacia abajo deterministas son estrictamente menos poderosos que sus contrapartes de árboles de abajo hacia arriba deterministas, porque las propiedades de árbol especificadas por los autómatas de árboles de arriba hacia abajo deterministas solo pueden depender de las propiedades de la ruta. (Los autómatas de árboles de abajo hacia arriba deterministas son tan poderosos como los autómatas de árboles ND).
Un autómata de árbol finito de abajo hacia arriba sobre F se define como una tupla ( Q , F , Q f , Δ), donde Q es un conjunto de estados, F es un alfabeto clasificado (es decir, un alfabeto cuyos símbolos tienen una aridad asociada ), Q f ⊆ Q es un conjunto de estados finales y Δ es un conjunto de reglas de transición de la forma f ( q 1 ( x 1 ),..., q n ( x n )) → q ( f ( x 1 ,..., x n )), para unas variables n -arias f ∈ F , q , q i ∈ Q y x i que denotan subárboles. Es decir, los miembros de Δ son reglas de reescritura desde los nodos cuyas raíces de hijos son estados hasta los nodos cuyas raíces son estados. Por lo tanto, el estado de un nodo se deduce de los estados de sus hijos.
Para n = 0, es decir, para un símbolo constante f , la definición de la regla de transición anterior dice f () → q ( f ()); a menudo se omiten los paréntesis vacíos por conveniencia: f → q ( f ). Dado que estas reglas de transición para símbolos constantes (hojas) no requieren un estado, no se necesitan estados iniciales definidos explícitamente. Un autómata de árbol de abajo hacia arriba se ejecuta en un término base sobre F , comenzando en todas sus hojas simultáneamente y moviéndose hacia arriba, asociando un estado de ejecución de Q con cada subtérmino. El término es aceptado si su raíz está asociada a un estado de aceptación de Q f . [1]
Un autómata de árbol finito de arriba hacia abajo sobre F se define como una tupla ( Q , F , Q i , Δ), con dos diferencias con los autómatas de árbol de abajo hacia arriba. Primero, Q i ⊆ Q , el conjunto de sus estados iniciales, reemplaza a Q f ; segundo, sus reglas de transición están orientadas inversamente: q ( f ( x 1 ,..., x n )) → f ( q 1 ( x 1 ),..., q n ( x n )), para unas variables n -arias f ∈ F , q , q i ∈ Q y x i que denotan subárboles. Es decir, los miembros de Δ son aquí reglas de reescritura desde nodos cuyas raíces son estados hasta nodos cuyas raíces de hijos son estados. Un autómata de arriba hacia abajo comienza en algunos de sus estados iniciales en la raíz y se mueve hacia abajo a lo largo de las ramas del árbol, asociando a lo largo de una carrera un estado con cada subtérmino de manera inductiva. Un árbol es aceptado si cada rama puede atravesarse de esta manera. [2]
Un autómata de árbol se denomina determinista (abreviado DFTA ) si no hay dos reglas de Δ que tengan el mismo lado izquierdo; de lo contrario, se denomina no determinista ( NFTA ). [3] Los autómatas de árbol de arriba hacia abajo no deterministas tienen el mismo poder expresivo que los de abajo hacia arriba no deterministas; [4] las reglas de transición simplemente se invierten y los estados finales se convierten en los estados iniciales.
Por el contrario, los autómatas de árbol deterministas de arriba hacia abajo [5] son menos potentes que sus contrapartes de abajo hacia arriba, porque en un autómata de árbol determinista no hay dos reglas de transición que tengan el mismo lado izquierdo. Para los autómatas de árbol, las reglas de transición son reglas de reescritura; y para los de arriba hacia abajo, el lado izquierdo serán los nodos padre. En consecuencia, un autómata de árbol determinista de arriba hacia abajo solo podrá probar las propiedades del árbol que sean verdaderas en todas las ramas, porque la elección del estado para escribir en cada rama hija se determina en el nodo padre, sin conocer el contenido de las ramas hijas.
Los autómatas de árbol infinito extienden los autómatas de arriba hacia abajo a árboles infinitos y pueden usarse para demostrar la decidibilidad de S2S , la teoría monádica de segundo orden con dos sucesores. Los autómatas de árbol finito (no deterministas si son de arriba hacia abajo) son suficientes para WS2S. [6]
Al emplear coloración para distinguir los miembros de F y Q , y usando el alfabeto clasificado F ={ false , true , nil , cons (.,.)}, con cons teniendo aridad 2 y todos los demás símbolos teniendo aridad 0, un autómata de árbol de abajo hacia arriba que acepta el conjunto de todas las listas finitas de valores booleanos se puede definir como ( Q , F , Q f , Δ) con Q = { Bool , BList }, Q f = { BList } y Δ que consiste en las reglas
En este ejemplo, las reglas se pueden entender intuitivamente como la asignación de su tipo a cada término de manera ascendente; por ejemplo, la regla (4) se puede leer como "Un término cons ( x 1 , x 2 ) tiene tipo BList , siempre que x 1 y x 2 tengan tipo Bool y BList , respectivamente". Una ejecución de ejemplo de aceptación es
Cf. la derivación del mismo término a partir de una gramática de árbol regular correspondiente al autómata, que se muestra en Gramática de árbol regular#Ejemplos .
Un ejemplo de ejecución de rechazo es
Intuitivamente, esto corresponde a que el término cons ( falso , verdadero ) no está bien tipificado.
Utilizando la misma coloración que antes, este ejemplo muestra cómo los autómatas de árbol generalizan autómatas de cadena ordinarios. El autómata de cadena determinista finito que se muestra en la imagen acepta todas las cadenas de dígitos binarios que denotan un múltiplo de 3. Utilizando las nociones de Automata finito determinista#Definición formal , se define por:
En la configuración del autómata de árbol, el alfabeto de entrada se cambia de modo que los símbolos 0 y 1 sean ambos unarios, y se utilice un símbolo nulo, por ejemplo, nil , para las hojas de los árboles. Por ejemplo, la cadena binaria " 110 " en la configuración del autómata de cadena corresponde al término " 1 ( 1 ( 0 ( nil )))" en la configuración del autómata de árbol; de esta manera, las cadenas se pueden generalizar a árboles o términos. El autómata de árbol finito de arriba hacia abajo que acepta el conjunto de todos los términos correspondientes a múltiplos de 3 en la notación de cadena binaria se define entonces por:
Por ejemplo, el árbol " 1 ( 1 ( 0 ( nil )))" es aceptado por la siguiente ejecución del autómata de árbol:
Por el contrario, el término " 1 ( 0 ( nulo ))" conduce a la siguiente ejecución del autómata que no lo acepta:
Dado que no hay otros estados iniciales que S 0 para iniciar la ejecución de un autómata, el término " 1 ( 0 ( nulo ))" no es aceptado por el autómata del árbol.
A modo de comparación, la tabla muestra en las columnas (A) y (D) una gramática regular (de cadena) (derecha) y una gramática regular de árbol , respectivamente, cada una de las cuales acepta el mismo lenguaje que su contraparte autómata.
Para un autómata de abajo hacia arriba, se acepta un término fundamental t (es decir, un árbol) si existe una reducción que comienza en t y termina en q ( t ), donde q es un estado final. Para un autómata de arriba hacia abajo, se acepta un término fundamental t si existe una reducción que comienza en q ( t ) y termina en t , donde q es un estado inicial.
El lenguaje de árbol L ( A ) aceptado , o reconocido , por un autómata de árbol A es el conjunto de todos los términos básicos aceptados por A. Un conjunto de términos básicos es reconocible si existe un autómata de árbol que lo acepta.
Un homomorfismo de árbol lineal (es decir, que preserva la aridad) preserva la reconocibilidad. [7]
Un autómata de árbol finito no determinista está completo si hay al menos una regla de transición disponible para cada combinación posible de símbolo-estado. Un estado q es accesible si existe un término fundamental t tal que existe una reducción de t a q ( t ). Un NFTA está reducido si todos sus estados son accesibles. [8]
Cada término fundamental t suficientemente grande [9] en un lenguaje de árbol reconocible L puede ser tripartido verticalmente [10] de tal manera que la repetición arbitraria ("bombeo") de la parte media mantenga el término resultante en L. [ 11] [12]
Para el lenguaje de todas las listas finitas de valores booleanos del ejemplo anterior, se pueden extraer todos los términos más allá del límite de altura k = 2, ya que deben contener una ocurrencia de cons . Por ejemplo,
Todos pertenecen a ese idioma.
La clase de lenguajes arbóreos reconocibles está cerrada bajo unión, bajo complementación y bajo intersección. [13]
Una congruencia en el conjunto de todos los árboles sobre un alfabeto clasificado F es una relación de equivalencia tal que u 1 ≡ v 1 y ... y u n ≡ v n implica f ( u 1 ,..., u n ) ≡ f ( v 1 ,..., v n ) , para cada f ∈ F . Es de índice finito si su número de clases de equivalencia es finito.
Para un árbol-lenguaje dado L , se puede definir una congruencia mediante u ≡ L v si C [ u ] ∈ L ⇔ C [ v ] ∈ L para cada contexto C .
El teorema de Myhill-Nerode para autómatas de árbol establece que las tres afirmaciones siguientes son equivalentes: [14]