Un autómata de árbol es un tipo de máquina de estado . Los autómatas de árbol se ocupan de estructuras de árbol , en lugar de las cadenas de máquinas de estado más convencionales.
El siguiente artículo trata sobre los autómatas de árboles ramificados, que corresponden a los lenguajes regulares de los árboles .
Al igual que con los autómatas clásicos, los autómatas de árbol finito (FTA) pueden ser un autómata determinista o no. Según cómo el autómata procese el árbol de entrada, los autómatas de árbol finito 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 árbol no deterministas (ND) de arriba hacia abajo y ND de abajo hacia arriba son equivalentes en poder expresivo, los autómatas deterministas de arriba hacia abajo son estrictamente menos poderosos que sus homólogos deterministas de abajo hacia arriba, porque las propiedades del árbol especificado por autómatas de árbol de arriba hacia abajo deterministas solo puede depender de las propiedades de la ruta. (Los autómatas de árbol ascendentes deterministas son tan poderosos como los autómatas de árbol ND).
Definiciones
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 una n -aria f ∈ F , q , q i ∈ Q , y x i variables que denotan subárboles. Es decir, los miembros de Δ son reglas de reescritura de nodos cuyas raíces de los hijos son estados, a nodos cuyas raíces son estados. Por 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, los paréntesis vacíos se omiten 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 básico sobre F , comenzando en todas sus hojas simultáneamente y moviéndose hacia arriba, asociando un estado de ejecución de Q con cada subtermo. El término se acepta 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 a la inversa: q ( f ( x 1 , ..., x n )) → f ( q 1 ( x 1 ), ..., q n ( x n )), para un n - ary f ∈ F , q , q i ∈ Q , y x i variables que denotan subárboles. Es decir, los miembros de Δ aquí reescriben reglas desde nodos cuyas raíces son estados a 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 subtermo de manera inductiva. Se acepta un árbol si todas las ramas se pueden atravesar de esta manera. [2]
Un autómata de árbol se llama 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, determinista árbol de autómatas de arriba hacia abajo [5] son menos potentes que sus contrapartes de abajo hacia arriba, porque en un árbol determinista autómata no hay dos reglas de transición tienen 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 padres. En consecuencia, un autómata de árbol de arriba hacia abajo determinista 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 secundaria se determina en el nodo principal, sin conocer el contenido de las ramas secundarias. .
Ejemplos de
Autómata ascendente que acepta listas booleanas
Emplear colores para distinguir los miembros de F y Q , y usar el alfabeto clasificado F = { falso , verdadero , nulo , contras (.,.)}, Donde los contras tienen aridad 2 y todos los demás símbolos tienen aridad 0, un árbol de abajo hacia arriba El autómata 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 consta de las reglas
falso | → | Bool ( falso ) | (1), |
cierto | → | Bool ( verdadero ) | (2), |
nulo | → | BList ( cero ) | (3) y |
contras ( Bool (x 1 ), BList (x 2 )) | → | BList ( contras (x 1 , x 2 )) | (4). |
En este ejemplo, se puede entender intuitivamente que las reglas asignan a cada término su tipo de forma ascendente; por ejemplo, la regla (4) se puede leer como "Un término cons ( x 1 , x 2 ) tiene el tipo BList , siempre que x 1 y x 2 tengan el tipo Bool y BList , respectivamente". Un ejemplo de ejecución de aceptación es
contras ( | falsa , | contras ( | verdadera , | nulo | )) | ||
⇒ | contras ( | falsa , | contras ( | verdadera , | BList ( cero ) | )) | por (3) |
⇒ | contras ( | falsa , | contras ( | Bool ( cierto ), | BList ( cero ) | )) | por (2) |
⇒ | contras ( | falsa , | BList ( contras ( | verdadera , | nulo | ))) | por (4) |
⇒ | contras ( | Bool ( falso ), | BList ( contras ( | verdadera , | nulo | ))) | por 1) |
⇒ | BList ( contras ( | falsa , | contras ( | verdadera , | nulo | ))) | por (4), aceptado. |
Cf. la derivación del mismo término 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
contras ( | falsa , | cierto | ) | ||
⇒ | contras ( | falsa , | Bool ( verdadero ) | ) | por 1) |
⇒ | contras ( | Bool ( falso ), | Bool ( verdadero ) | ) | por (2), no se aplica ninguna otra regla. |
Intuitivamente, esto corresponde a que el término contras ( falso , verdadero ) no está bien escrito.
Autómata descendente que acepta múltiplos de 3 en notación binaria
(A) | (B) | (C) | (D) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Reglas gramaticales de cadenas | Transiciones de autómatas de cadena | Transiciones de árboles autómatas | Reglas gramaticales del árbol | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
Utilizando la misma coloración anterior, este ejemplo muestra cómo los autómatas de árbol generalizan los 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. Usando las nociones del autómata finito determinista # Definición formal , se define por:
- el conjunto Q de estados es { S 0 , S 1 , S 2 },
- el alfabeto de entrada es { 0 , 1 },
- el estado inicial es S 0 ,
- el conjunto de estados finales es { S 0 }, y
- siendo las transiciones las que se muestran en la columna (B) de la tabla.
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 un símbolo nular, digamos nulo, se usa 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 forma, 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 notación de cadena binaria se define entonces por:
- el conjunto Q de estados sigue siendo { S 0 , S 1 , S 2 },
- el alfabeto de entrada clasificado es { 0 , 1 , nil }, con Arity ( 0 ) = Arity ( 1 ) = 1 y Arity ( nil ) = 0, como se explicó,
- el conjunto de estados iniciales es { S 0 }, y
- siendo las transiciones las que se muestran en la columna (C) de la tabla.
Por ejemplo, el árbol " 1 ( 1 ( 0 ( nil )))" es aceptado por la siguiente ejecución del autómata de árbol:
S 0 ( | 1 ( | 1 ( | 0 ( | nulo | )))) | |||||
⇒ | 1 ( | S 1 ( | 1 ( | 0 ( | nulo | )))) | por 2 | |||
⇒ | 1 ( | 1 ( | S 0 ( | 0 ( | nulo | )))) | por 4 | |||
⇒ | 1 ( | 1 ( | 0 ( | S 0 ( | nulo | )))) | por 1 | |||
⇒ | 1 ( | 1 ( | 0 ( | nulo | ))) | por 0 |
Por el contrario, el término " 1 ( 0 ( nil ))" conduce a la siguiente ejecución del autómata que no acepta:
⇒ S 0 ( | 1 ( | 0 ( | nulo | ))) | |||
⇒ | 1 ( | S 1 ( | 0 ( | nulo | )))) | por 2 | |
⇒ | 1 ( | 0 ( | S 2 ( | nulo | )))) | por 3, no se aplica ninguna otra regla |
Dado que no hay otros estados iniciales que S 0 para iniciar la ejecución de un autómata, el término " 1 ( 0 ( nil ))" no es aceptado por el árbol autómata.
Para propósitos de comparación, la tabla da en la columna (A) y (D) una gramática regular (de cadena) (derecha) y una gramática de árbol regular , respectivamente, cada una aceptando el mismo lenguaje como su contraparte autómata.
Propiedades
Reconocibilidad
Para un autómata ascendente, 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 básico t si existe una reducción que comienza en q ( t ) y termina en t , donde q es un estado inicial.
El lenguaje árbol de L ( A ) aceptado o reconocido , por un árbol autómata A es el conjunto de todos los términos aceptados por tierra Una . Un conjunto de términos básicos es reconocible si existe un árbol autómata que lo acepta.
Un homomorfismo de árbol lineal (es decir, que conserva la aridad) conserva la reconocibilidad. [6]
Completitud y reducción
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 ). Una NFTA se reduce si todos sus estados son accesibles. [7]
Lema de bombeo
Cada suficientemente grande [8] suelo término t en un idioma árbol reconocible L se puede tripartited verticalmente [9] de tal manera que la repetición arbitraria ( "bombeo") de la parte media mantiene el término que resulta en L . [10] [11]
Para el lenguaje de todas las listas finitas de valores booleanos del ejemplo anterior, se pueden bombear todos los términos más allá del límite de altura k = 2, ya que deben contener una ocurrencia de contras . Por ejemplo,
contras ( falso , | contras ( verdadero , nulo ) | ) | , |
contras ( falso , contras ( falso , | contras ( verdadero , nulo ) | )) | , |
contras ( falso , contras ( falso , contras ( falso , | contras ( verdadero , nulo ) | ))) | ... |
todos pertenecen a ese idioma.
Cierre
La clase de lenguajes de árbol reconocibles está cerrada bajo unión, bajo complementación y bajo intersección. [12]
Teorema de Myhill-Nerode
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 lenguaje árbol dado L , una congruencia puede ser definido por u ≡ L v si C [ u ] ∈ L ⇔ C [ v ] ∈ L para cada contexto C .
El teorema de Myhill-Nerode para árboles autómatas establece que las siguientes tres afirmaciones son equivalentes: [13]
- L es un lenguaje de árbol reconocible
- L es la unión de algunas clases de equivalencia de una congruencia de índice finito
- la relación ≡ L es una congruencia de índice finito
Ver también
- Teorema de Courcelle : una aplicación de autómatas de árbol para demostrar un metateorema algorítmico sobre gráficos
- Transductores de árbol : amplían los autómatas de árbol de la misma forma que los transductores de palabras amplían los autómatas de palabras .
- Autómatas de árboles alternos
- Autómatas de árbol infinito
Notas
- ^ Comon y col. 2008 , secc. 1.1, pág. 20.
- ^ Comon y col. 2008 , secc. 1.6, pág. 38.
- ^ Comon y col. 2008 , secc. 1.1, pág. 23.
- ^ Comon y col. 2008 , secc. 1.6, teorema 1.6.1, pág. 38.
- ^ En un sentido estricto, los autómatas de arriba hacia abajo deterministas no están definidos por Comon et al. (2008) pero se utilizan allí (sección 1.6, proposición 1.6.2, p. 38). Aceptan la clase de lenguajes de árbol de camino cerrado (sección 1.8, ejercicio 1.6, p. 43-44).
- ^ La noción en Comon et al. (2008 , secc. 1.4, teorema 1.4.3, p. 31-32) del homomorfismo del árbol es más general que el del artículo " homomorfismo del árbol ".
- ^ Comon y col. 2008 , secc. 1.1, pág. 23-24.
- ^ Formalmente: altura ( t )> k , con k > 0 dependiendo solo de L , no de t
- ^ Formalmente: hay un contexto C [.], Un contexto no trivial C '[.] Y un término básico u tal que t = C [ C ' [ u ]]. Un "contexto" C [.] Es un árbol con un agujero (o, en consecuencia, un término con una aparición de una variable). Un contexto se denomina "trivial" si el árbol consta solo del nodo del hueco (o, en consecuencia, si el término es solo la variable). La notación C [ t ] significa el resultado de insertar el árbol t en el hueco de C [.] (O, en consecuencia, instanciar la variable at ). Comon y col. 2008 , pág. 17, da una definición formal.
- ^ Formalmente: C [ C ' n [ u ]] ∈ L para todo n ≥ 0. La notación C n [.] Significa el resultado de apilar n copias de C [.] Una en otra, cf. Comon y col. 2008 , pág. 17.
- ^ Comon y col. 2008 , secc. 1.2, pág. 29.
- ^ Comon y col. 2008 , secc. 1.3, teorema 1.3.1, pág. 30.
- ^ Comon y col. 2008 , secc. 1.5, pág .36.
Referencias
- Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (noviembre de 2008). Técnicas y aplicaciones de Tree Automata (PDF) . Consultado el 11 de febrero de 2014 .
- Hosoya, Haruo (4 de noviembre de 2010). Fundamentos del procesamiento XML: el enfoque Tree-Automata . Prensa de la Universidad de Cambridge. ISBN 978-1-139-49236-2.
enlaces externos
Implementaciones
- Grappa : bibliotecas de autómatas de árbol clasificadas y no clasificadas (OCaml)
- Timbuk : herramientas para análisis de accesibilidad y cálculos de autómatas de árboles (OCaml)
- LETHAL - biblioteca para trabajar con árboles finitos y autómatas de cobertura (Java)
- Biblioteca de autómatas de árbol comprobada por máquina (Isabelle [OCaml, SML, Haskell])
- VATA : una biblioteca para la manipulación eficiente de autómatas de árbol no deterministas (C ++)