En informática teórica y teoría del lenguaje formal , una gramática de árbol regular ( RTG ) es una gramática formal que describe un conjunto de árboles o términos dirigidos . [1] Una gramática de palabras normal puede verse como un tipo especial de gramática de árbol regular, que describe un conjunto de árboles de ruta única .
Definición
Una gramática de árbol regular G está definida por la tupla
G = ( N , Σ, 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 á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: cualquier árbol que se puede derivar de Z utilizando el conjunto de reglas P se dice que está descrito por G . Este conjunto de árboles es conocido como el lenguaje 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 en 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 en él; si S es un contexto tal, 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 compuestas de símbolos de Σ, mientras ⇒ G * denota aplicaciones sucesivas de ⇒ G .
Un lenguaje generado por alguna gramática de árbol regular se denomina lenguaje de árbol regular .
Ejemplos de
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 , cons (.,.)} Es nuestro alfabeto clasificado, aridades indicadas por argumentos ficticios (es decir, el símbolo cons tiene aridad 2),
- Z 1 = BList es nuestro no terminal inicial, y
- el conjunto P 1 consta de las siguientes producciones:
- Bool → falso
- Bool → verdadero
- BList → cero
- BList → contras ( Bool , BList )
Un ejemplo de derivación de la gramática G 1 es
BList ⇒ contras ( Bool , BList ) ⇒ contras ( falso , contras ( Bool , BList )) ⇒ contras ( falso , contras ( verdadero , nulo )).
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 ML estándar ):
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 ML estándar de tipo BList.
Para otro ejemplo, sea G 2 = ( N 1 , Σ 1 , BList1 , P 1 ∪ P 2 ), utilizando el conjunto no terminal y el alfabeto de arriba, pero ampliando el conjunto de producción por P 2 , que consta de las siguientes producciones:
- BList1 → contras ( verdadero , BList )
- BList1 → contras ( falso , BList1 )
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 ML estándar, ni en ningún otro lenguaje funcional. Es un subconjunto propio de L ( G 1 ). El término de ejemplo anterior también está en L ( G 2 ), como muestra la siguiente derivación:
BList1 ⇒ contras ( falso , BList1 ) ⇒ contras ( falso , contras ( verdadero , BList )) ⇒ contras ( falso , contras ( verdadero , nulo )).
Propiedades del idioma
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 se puede decidir si L 1 ⊆ L 2 y si L 1 = L 2 .
Caracterizaciones alternativas y relación con otros lenguajes formales
- Las gramáticas de árbol 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 árbol binarios regulares con palabras anidadas y lenguajes visiblemente pushdown . [3] [4]
Aplicaciones
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 lógica de primer orden de fórmulas sobre la igualdad (=) y establecer la pertenencia (∈) como los únicos predicados [6]
- Resolver 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 de gráficos [9]
Ver también
- Establecer restricción : una generalización de las gramáticas de árbol regulares
- Gramática adyacente al árbol
Referencias
- ^ "Gramáticas de árboles regulares como formalismo para la subespecificación del alcance". CiteSeerX 10.1.1.164.5484 . Cite journal requiere
|journal=
( ayuda ) - ^ Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 de octubre de 2007). "Técnicas y aplicaciones de Tree Automata" . Consultado el 25 de enero de 2016 .
- ^ Alur, R .; Madhusudan, P. (2004). "Idiomas visiblemente pushdown" (PDF) . Actas del trigésimo sexto simposio anual ACM sobre teoría de la computación - STOC '04 . págs. 202–211. doi : 10.1145 / 1007352.1007390 . ISBN 978-1581138528. Sección 4, Teorema 5,
- ^ Alur, R .; Madhusudan, P. (2009). "Añadiendo estructura de anidamiento a las palabras" (PDF) . Revista de la ACM . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . doi : 10.1145 / 1516512.1516518 . Sección 7
- ^ Emmelmann, Helmut (1991). "Selección de código por reescritura de términos controlados regularmente". Generación de código: conceptos, herramientas, técnicas . Talleres de Informática. 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). "Resolver sistemas de restricciones de conjunto utilizando autómatas de árbol". X Simposio Anual sobre Aspectos Teóricos de la Informática . LNCS. 665 . Saltador. págs. 505–514.
- ^ Burghardt, Jochen (2002). "Axiomatización de álgebras finitas". Avances en Inteligencia Artificial . LNAI. 2479 . Saltador. págs. 222-234. arXiv : 1403.7347 . Código bibliográfico : 2014arXiv1403.7347B . ISBN 3-540-44185-9.
- ^ Ziv-Ukelson, Smoly (2016). Algoritmos para la búsqueda de redes de gramática de árboles regulares y su aplicación a la minería de patrones de infección viral humana . J. de Comp. Bio. [1]
Otras lecturas
- Las gramáticas regulares de árboles ya fueron descritas en 1968 por:
- Brainerd, WS (1968). "La minimalización de árboles autómatas" . Información y control . 13 (5): 484–491. doi : 10.1016 / s0019-9958 (68) 90917-0 .
- Thatcher, JW; Wright, JB (1968). "Teoría generalizada de autómatas finitos con aplicación a un problema de decisión de lógica de segundo orden". Teoría de sistemas matemáticos . 2 (1): 57–81. doi : 10.1007 / BF01691346 .
- Un libro dedicado a las gramáticas de los árboles es: Nivat, Maurice; Podelski, Andreas (1992). Autómatas e idiomas de árboles . Estudios en Informática e Inteligencia Artificial. 10 . Holanda Septentrional.
- Los algoritmos de las gramáticas de árbol regulares se discuten desde una vista orientada a la eficiencia en: Aiken, A .; Murphy, B. (1991). "Implementación de expresiones de árboles regulares". Conferencia ACM sobre lenguajes de programación funcional y arquitectura informática . 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 ruta más corta 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 idioma en orden de peso creciente. En particular, cualquier no terminal con un peso mínimo infinito produce el lenguaje vacío. Ver: 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 árbol regulares se han generalizado para admitir pruebas de igualdad entre nodos hermanos en árboles. Ver: Bogaert, B .; Tison, Sophie (1992). "Restricciones de igualdad y desigualdad en subtérminos directos en árboles autómatas". Proc. Noveno STACS . LNCS. 577 . Saltador. págs. 161-172.
- Permitir pruebas de igualdad entre nodos más profundos conduce a la indecidibilidad. Ver: Tommasi, M. (1991). Automates d'Arbres avec Tests d'Égalités entre Cousins Germains . LIFL-IT.