gramática de árbol regular

En la informática teórica y la teoría del lenguaje formal , una gramática de árbol regular es una gramática formal que describe un conjunto de árboles dirigidos o términos . ^{[ 1 ]} Una gramática de palabras regular puede considerarse un tipo especial de gramática de árbol regular, que describe un conjunto de árboles de ruta única .

Una gramática de árbol regular G se define mediante la tupla G = ( N , Σ, Z , P ), donde:

• N es un conjunto finito de no terminales,
• Σ es un alfabeto jerarquizado (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 álgebra de términos asociada , es decir el conjunto de todos los árboles compuestos a partir de símbolos en Σ ∪ N según sus aridades, donde los no terminales se consideran nulos.

La gramática G define implícitamente un conjunto de árboles: cualquier árbol que pueda derivarse de Z utilizando el conjunto de reglas P se dice que está descrito por G. Este conjunto de árboles se conoce como el lenguaje de G. Formalmente, la relación ⇒ _G en el conjunto T _Σ ( N ) se define de la siguiente manera:

Un árbol t ₁ ∈ T _Σ ( N ) puede derivarse en un solo paso en un árbol t ₂ ∈ T _Σ ( N ) (en resumen: t ₁ ⇒ _G t ₂ ), si existe un contexto S y una producción ( A → t ) ∈ P tales que:

• t ₁ = S [ A ], y
• t ₂ = 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 .

Sea G ₁ = ( N ₁ ,Σ ₁ , Z ₁ , P ₁ ), donde

• N ₁ = { Bool , BList } es nuestro conjunto de no terminales,
• Σ ₁ = { true , false , nil , cons (.,.) } es nuestro alfabeto clasificado, las aridades indicadas por argumentos ficticios (es decir, el símbolo cons tiene aridad 2),
• Z ₁ = BList es nuestro no terminal inicial, y
• El conjunto P ₁ consta de las siguientes producciones:
  • Booleano → falso
  • Booleano → verdadero
  • BList → nulo
  • BList → contras ( Bool , BList )

Un ejemplo de derivación de la gramática G ₁ es

BList ⇒ cons ( Bool , BList ) ⇒ cons ( false , cons ( Bool , BList )) ⇒ cons ( false , cons ( true , nil )).

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 ₁ es el conjunto de todas las listas finitas de valores booleanos, es decir, L ( G ₁ ) resulta ser igual a T _Σ1 . La gramática G ₁ corresponde a las declaraciones de tipos de datos algebraicos (en el lenguaje de programación Standard ML ):

tipo de dato Bool = false | verdadero tipo de dato BList = nil | cons de Bool * BList

Cada miembro de L ( G ₁ ) corresponde a un valor Standard-ML de tipo BList.

Para otro ejemplo, sea G ₂ = ( N ₁ , Σ ₁ , BList ₁ , P ₁ ∪ P ₂ ) , utilizando el conjunto no terminal y el alfabeto de arriba, pero extendiendo el conjunto de producción por P ₂ , que consta de las siguientes producciones:

• BList ₁ → contras ( verdadero , BList )
• BList ₁ → contras ( falso , BList ₁ )

El lenguaje L ( G₂ ₎ es el conjunto de todas las listas finitas de valores booleanos que contienen _verdadero al menos una vez. El conjunto _L ( G₂ ) no tiene un tipo de dato equivalente en Standard ML, ni en ningún otro lenguaje funcional. Es un subconjunto propio de L ( G₁ ). El término del ejemplo anterior también pertenece a L ( G₂ ), como muestra _la siguiente derivación:

BList ₁ ⇒ contras ( falso , BList ₁ ) ⇒ contras ( falso , contras ( verdadero , BList )) ⇒ contras ( falso , contras ( verdadero , nulo )).

Si L ₁ , L ₂ son ambos lenguajes de árbol regulares, entonces los conjuntos de árboles L ₁ ∩ L ₂ , L ₁ ∪ L ₂ , y L ₁ \ L ₂ también son lenguajes de árbol regulares, y es decidible si L ₁ ⊆ L ₂ , y si L ₁ = L ₂ .

• Las gramáticas de árboles regulares son una generalización de las gramáticas de palabras regulares .
• Los lenguajes de árbol regulares son también los lenguajes reconocidos por los autómatas de árbol ascendentes y los autómatas de árbol descendentes no deterministas. ^{[ 2 ]}
• Rajeev Alur y Parthasarathy Madhusudan relacionaron una subclase de lenguajes de árboles binarios regulares con palabras anidadas y lenguajes visiblemente apilados . ^{[ 3 ] [ 4 ]}

Las aplicaciones de las gramáticas de árboles regulares incluyen:

• Selección de instrucciones en la generación de código del compilador ^{[ 5 ]}
• Un procedimiento de decisión para la teoría de la lógica de primer orden de fórmulas sobre igualdad (=) y pertenencia a un conjunto (∈) como únicos predicados ^{[ 6 ]}
• Resolución de restricciones sobre conjuntos matemáticos ^{[ 7 ]}
• El conjunto de todas las verdades expresables en lógica de primer orden sobre un álgebra finita (que siempre es un lenguaje de árbol regular) ^{[ 8 ]}
• Búsqueda en grafos ^{[ 9 ]}

• Restricción de conjuntos : una generalización de las gramáticas de árboles regulares.
• Gramática de adjunción de árboles

• Las gramáticas de árboles regulares ya fueron descritas en 1968 por:
  • Brainerd, WS (1968). "La minimización de los autómatas de árbol" . Information and 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 autómatas finitos con una aplicación a un problema de decisión de lógica de segundo orden". Mathematical Systems Theory . 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 de árboles y lenguajes . Estudios en informática e inteligencia artificial. Vol. 10. North-Holland. 
• Los algoritmos sobre gramáticas de árboles regulares se analizan desde una perspectiva orientada a la eficiencia en: Aiken, A.; Murphy, B. (1991). "Implementing Regular Tree Expressions". ACM Conference on Functional Programming Languages ​​and Computer Architecture . pp. 427– 447. CiteSeerX 10.1.1.39.3766 .  
• Dada una correspondencia entre árboles y pesos, la generalización del algoritmo de Dijkstra para encontrar el camino más corto, propuesta por Donald Knuth, puede aplicarse a una gramática de árboles 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 creciente de peso. En particular, cualquier no terminal con peso mínimo infinito produce el lenguaje vacío. Véase: Knuth, DE (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters . 6 (1): 1– 5. doi : 10.1016/0020-0190(77)90002-3 .
• Los autómatas de árbol regulares se han generalizado para admitir pruebas de igualdad entre nodos hermanos en árboles. Véase: Bogaert, B.; Tison, Sophie (1992). "Equality and Disequality Constraints on Direct Subterms in Tree Automata". Proc. 9th STACS . LNCS. Vol. 577. Springer. pp. 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.