Una gramática de árbol regular G está definida por la tupla
GRAMO = ( norte , Σ, Z , P ),
dónde
N es un conjunto finito de no terminales,
Σ es un alfabeto clasificado (es decir, un alfabeto cuyos símbolos tienen una aridad asociada ) disjunto de N ,
Z es el no terminal inicial, con Z ∈ N , y
P es un conjunto finito de producciones de la forma A → t , con A ∈ N , y t ∈ T Σ ( N ) , donde T Σ ( N ) es el término asociado de álgebra , es decir, el conjunto de todos los árboles compuestos por símbolos en Σ ∪ N según sus aridades, donde los no terminales se consideran nulos.
Derivación de árboles
La gramática G define implícitamente un conjunto de árboles: se dice que cualquier árbol que pueda derivarse de Z utilizando el conjunto de reglas P está descrito por G. Este conjunto de árboles se conoce como lengua de G. Más formalmente, la relación ⇒ G en el conjunto T Σ ( N ) se define de la siguiente manera:
Un árbol t 1 ∈ T Σ ( N ) se puede derivar en un solo paso a un árbol t 2 ∈ T Σ ( N )
(en resumen: t 1 ⇒ G t 2 ), si hay un contexto S y una producción ( A → t ) ∈ P tal que:
t 1 = S [ A ], y
t 2 = S [ t ].
Aquí, un contexto significa un árbol con exactamente un agujero; si S es tal contexto, S [ t ] denota el resultado de llenar el árbol t en el agujero de S.
El lenguaje de árbol generado por G es el lenguaje L ( G ) = { t ∈ T Σ | Z ⇒ G * t } .
Aquí, T Σ denota el conjunto de todos los árboles compuestos por símbolos de Σ, mientras que ⇒ G * denota aplicaciones sucesivas de ⇒ G .
Un lenguaje generado por alguna gramática de árbol regular se llama lenguaje de árbol regular .
Ejemplos
Ejemplo de árbol de derivación de G 1 en notación lineal (tabla superior izquierda) y gráfica (imagen principal)
Sea G 1 = ( N 1 ,Σ 1 , Z 1 , P 1 ), donde
N 1 = { Bool , BList } es nuestro conjunto de no terminales,
Σ 1 = { verdadero , falso , nulo , contras (.,.) } es nuestro alfabeto clasificado, las aridades se indican mediante argumentos ficticios (es decir, el símbolo contras tiene aridad 2),
La imagen muestra el árbol de derivación correspondiente ; es un árbol de árboles (imagen principal), mientras que un árbol de derivación en gramáticas de palabras es un árbol de cadenas (tabla superior izquierda).
El lenguaje de árbol generado por G 1 es el conjunto de todas las listas finitas de valores booleanos, es decir, L ( G 1 ) resulta ser igual a T Σ1 . La gramática G 1 corresponde a las declaraciones de tipos de datos algebraicos (en el lenguaje de programación Standard ML ):
tipo de datos Bool = falso | verdadero tipo de datos BList = nil | contras de Bool * BList
Cada miembro de L ( G 1 ) corresponde a un valor Standard-ML de tipo BList.
Para otro ejemplo, sea G 2 = ( N 1 , Σ 1 , BList 1 , P 1 ∪ P 2 ) , usando el conjunto no terminal y el alfabeto de arriba, pero extendiendo el conjunto de producción por P 2 , que consta de las siguientes producciones:
BList 1 → contras ( verdadero , BList )
BList 1 → contras ( falso , BList 1 )
El lenguaje L ( G 2 ) es el conjunto de todas las listas finitas de valores booleanos que contienen verdadero al menos una vez. El conjunto L ( G 2 ) no tiene contraparte de tipo de datos en Standard ML ni en ningún otro lenguaje funcional. Es un subconjunto propio de L ( G 1 ). El término del ejemplo anterior también está en L ( G 2 ), como lo muestra la siguiente derivación:
Si L 1 , L 2 son lenguajes de árbol regulares, entonces los conjuntos de árboles L 1 ∩ L 2 , L 1 ∪ L 2 y L 1 \ L 2 también son lenguajes de árbol regulares, y es decidible si L 1 ⊆ L 2 , y si L 1 = L 2 .
Caracterizaciones alternativas y relación con otros lenguajes formales.
^ "Gramáticas de árboles regulares como formalismo para la subespecificación del alcance". CiteSeerX 10.1.1.164.5484 .
^ Común, Hubert; Dauchet, Max; Gilleron, Remi; Loding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 de octubre de 2007). "Técnicas y aplicaciones de autómatas de árboles" . Consultado el 25 de enero de 2016 .
^ Alur, R.; Madhusudan, P. (2004). "Idiomas visiblemente desplazados" (PDF) . Actas del trigésimo sexto simposio anual de ACM sobre teoría de la informática - STOC '04. págs. 202-211. doi :10.1145/1007352.1007390. ISBN978-1581138528. S2CID 7473479.Sección 4, Teorema 5,
^ Alur, R.; Madhusudan, P. (2009). "Agregar estructura anidada a las palabras" (PDF) . Revista de la ACM . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . doi :10.1145/1516512.1516518. S2CID 768006. Sección 7
^ Emmelmann, Helmut (1991). "Selección de código mediante reescritura de términos controlada periódicamente". Generación de código: conceptos, herramientas y técnicas . Talleres de Computación. Saltador. págs. 3–29.
^ Comon, Hubert (1990). "Fórmulas ecuacionales en álgebras ordenadas por orden". Proc. ICALP .
^ Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Resolución de sistemas de restricciones establecidas utilizando autómatas de árbol". Décimo Simposio Anual sobre Aspectos Teóricos de la Informática . LNCS. vol. 665. Saltador. págs. 505–514.
^ Ziv-Ukelson, Smoly (2016). "Algoritmos para la búsqueda de redes de gramática de árboles regulares y su aplicación a la extracción de patrones de infección viral humana" . J. de Comp. Biografía.[1]
Lectura adicional
Las gramáticas de árboles regulares ya fueron descritas en 1968 por:
Brainerd, WS (1968). "La minimización de los autómatas de árboles". Información y Control . 13 (5): 484–491. doi : 10.1016/s0019-9958(68)90917-0 . hdl : 10945/40204 .
Thatcher, JW; Wright, JB (1968). "Teoría generalizada de los autómatas finitos con una aplicación a un problema de decisión de la lógica de segundo orden". Teoría de Sistemas Matemáticos . 2 (1): 57–81. doi :10.1007/BF01691346. S2CID 31513761.
Un libro dedicado a las gramáticas de árboles es: Nivat, Maurice; Podelski, Andreas (1992). Autómatas y lenguajes de árboles . Estudios en Informática e Inteligencia Artificial. vol. 10. Holanda Septentrional.
Los algoritmos sobre gramáticas de árboles regulares se analizan desde una visión orientada a la eficiencia en: Aiken, A.; Murphy, B. (1991). "Implementación de expresiones de árbol regulares". Conferencia ACM sobre Lenguajes de Programación Funcionales y Arquitectura de Computadores . págs. 427–447. CiteSeerX 10.1.1.39.3766 .
Dado un mapeo de árboles a pesos, la generalización de Donald Knuth del algoritmo de camino más corto de Dijkstra se puede aplicar a una gramática de árbol regular para calcular para cada no terminal el peso mínimo de un árbol derivable. Con base en esta información, es sencillo enumerar su lenguaje en orden de peso creciente. En particular, cualquier no terminal con peso mínimo infinito produce el lenguaje vacío. Véase: Knuth, DE (1977). "Una generalización del algoritmo de Dijkstra". Cartas de procesamiento de información . 6 (1): 1–5. doi :10.1016/0020-0190(77)90002-3.
Los autómatas de árboles regulares se han generalizado para admitir pruebas de igualdad entre nodos hermanos en los árboles. Ver: Bogaert, B.; Tison, Sophie (1992). "Restricciones de igualdad y desigualdad en subtérminos directos en autómatas de árboles". Proc. 9º STAC . LNCS. vol. 577. Saltador. págs. 161-172.
Permitir pruebas de igualdad entre nodos más profundos conduce a la indecidibilidad. Véase: Tommasi, M. (1991). Automates d'Arbres avec Tests d'Égalités entre Cousins Germains . LIFL-IT.
