Gramática de árvore regular

Em informática teórica e teoria das linguagens formais, uma gramática de árvore regular (RTG) é uma gramática formal que descreve o conjunto de árvores direcionais, ou termos. A gramática regular pode ser vista como um tipo especial de gramática de árvore regular, descrevendo um conjunto de árvores de caminho único.

Definição

Uma gramática de árvore regular G é definida pela tupla

G = (N, Σ, Z, P),

onde

• N é um conjunto de não-terminais,
• Σ é o alfabeto ranqueado (i.e., um alfabeto cujos símbolos possuem uma aridade associada) disjunto de N,
• Z é a variável não-terminal inicial, com Z ∈ N, e
• P é o conjunto de produções da forma A → t, com A ∈ N, e t ∈ T_Σ(N), onde T_Σ(N) é o universo de Herbrand associado, i.e. o conjunto de todas as árvores compostas pelos símbolos em Σ ∪ N de acordo com suas aridades, onde não-terminais são considerados nulários.

Derivações de Árvores

A gramática G, implicitamente, define um conjunto de árvores onde qualquer árvore que possa ser derivada de Z usando o conjunto de regras P é dita como sendo gerada por G. Esse conjunto de árvores é conhecido como o conjunto de linguagens de G. Mais formalmente, a relação ⇒_G no conjunto T_Σ(N) é definida da seguinte forma:

Uma árvore t₁∈ T_Σ(N) pode ser derivada em um único passo numa árvore t₂ ∈ T_Σ(N) (resumindo: t₁ ⇒_G t₂), se existe um contexto S e uma produção (A→t) ∈ P como no exemplo:

• t₁ = S[A], e
• t₂ = S[t].

Aqui, um contexto significa uma árvore com exatamente uma lacuna; se S é esse contexto, S[t] denota o resultado de preencher a árvore t na lacuna de S.

A linguagem de árvores gerada por G é a linguagem L(G) = { t ∈ T_Σ | Z ⇒_G* t }.

Aqui, T_Σ denota o conjunto de todas as árvores compostas de símbolos de Σ, enquanto ⇒_G* denota aplicações sucessivas de ⇒_G.

Uma linguagem gerada por uma gramática de árvore regular é uma linguagem de árvores regular.

Exemplos

Exemplo árvore de derivação G₁ em notação linear (tabela no canto superior esquerdo) e gráfica (figura principal)

Seja G₁ = (N₁,Σ₁,Z₁,P₁), onde

• N₁ = {Bool, BList } é o nosso conjunto de não-terminais,
• Σ₁ = { true, false, nil, cons(.,.) } é o nosso alfabeto ranqueado, aridades indicados pelos argumentos (i.e. o símbolo cons tem peso 2),
• Z₁ = BList é o nosso não-terminal inicial, e
• o conjunto P₁ consiste nas seguintes produções:
  • Bool → false
  • Bool → true
  • BList → nil
  • BList → cons(Bool,BList)

Um exemplo de derivação da gramática G₁ é

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

A imagem demonstra a árvore de derivação correspondente; ela é uma árvore de árvores (figura principal), enquanto que a árvore de derivação da gramática de termos é uma árvore de cadeias (tabela no canto superior esquerdo).

A árvore gerada por G₁ é o conjunto de todas as listas finitas de valores booleanos L(G₁), que é igual a T_Σ1. A gramática G₁ corresponde a declaração de tipos algébricos

  datatype Bool
    = false
    | true
  datatype BList
    = nil
    | cons of Bool * BList

na linguagem de programação Standard ML: todos os membros de L(G₁) correspondem a um valor do tipo BList em Standard ML.

Em outro exemplo, seja G₂ = (N₁,Σ₁,BList1,P₁ ∪ P₂), usando o conjunto de não-terminais e o alfabeto definidos no exemplo anterior, mas estendendo o conjunto de produções anterior com P₂, consistindo das seguintes produções:

• BList1 → cons(true,BList)
• BList1 → cons(false,BList1)

A linguagem L(G₂) é o conjunto de todas as listas finitas de valores booleanos que contém true em pelo menos um item. O conjunto L(G₂) não possui tipo de dado equivalente em Standard ML, nem em nenhuma outra linguagem funcional. Ele um conjunto próprio de L(G₁). O termo do exemplo acima por acaso está em L(G₂), tambpem, como mostra a derivação a seguir:

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

Propriedades da Linguagem

Se ambos L₁, L₂ são linguagens de árvores regulares, então os conjuntos de árvores L₁ ∩ L₂, L₁ ∪ L₂, e L₁ \ L₂ também são linguagens de árvores regulares, e é decidível tanto para L₁ ⊆ L₂, quanto para L₁ = L₂.

Caracterizações adicionais e relações com outras linguagens formais

Rajeev Alur e Parthasarathy Madhusudan relacionaram uma subclasse de linguagens de árvores binárias regulares a palavras aninhadas e linguagens visivelmente com pilha.

As linguagens de árvores regulares também são as linguagens reconhecidas por Autômatos de árvore ascendentes e autômatos de árvore não-derterminísticos descendentes.

Gramáticas de árvores regulares são generalizações de Gramáticas Regulares.

Ver também

• Cláusulas sob conjuntos — uma generalização de gramáticas de árvores regulares
• Gramática árvore-adjacente

Leitura adicional

• Um livro dedicado a gramáticas de árvore: Nivat, Maurice; Podelski, Andreas (1992). Tree Automata and Languages. Col: Studies in Computer Science and Artificial Intelligence. 10. [S.l.]: North-Holland 
• Gramáticas de árvores regulares já haviam sido descritas em 1968 por:
  • Brainerd, Walter S. (1 de novembro de 1968). «The minimalization of tree automata». Information and Control. 13 (5): 484-491. doi:10.1016/S0019-9958(68)90917-0 
  • Thatcher, J.W.; Wright, J.B. (1968). «Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic». Mathematical Systems Theory. 2 (1) 
• As aplicações de gramáticas de árvores regulares incluem:
  • Seleção de Instruções em geração de código de compiladores:Emmelmann, Helmut (1991). «Code Selection by Regularly Controlled Term Rewriting». Code Generation - Concepts, Tools, Techniques. Workshops in Computing. Springer. pp. 3–29 
  • Um Problema de decisão para a lógica de primeira ordem, teoria formal de fórmulas sobre equivalência equivalência (=) e pertinência em conjuntos (∈) como únicos predicados: Comon, Hubert (1990). «Equational Formulas in Order-Sorted Algebras». Proc. ICALP 
  • Resolver cláusulas sobre conjuntos: Gilleron, R.; Tison, S.; Tommasi, M. (1993). «Solving Systems of Set Constraints using Tree Automata». 10th Annual Symposium on Theoretical Aspects of Computer Science. LNCS. 665. Springer. pp. 505–514 
  • O conjunto de todas as verdades que podem ser expressas na lógica de primeira ordem sobre uma algebra finita é sempre uma gramática de árvore regular: Burghardt, Jochen (2002). «Axiomatization of Finite Algebras» (PDF). Advances in Artificial Intelligence. LNAI. 2479. Springer. pp. 222–234. ISBN 3-540-44185-9 
• Algoritmos sobre gramáticas de árvore regular são discutidos a partir de uma visão orientada pela eficiência em: Aiken, A.; Murphy, B. (1991). «Implementing Regular Tree Expressions». ACM Conference on Functional Programming Languages and Computer Architecture. pp. 427–447 
• Dado um mapeamento de árvores em pesos, a generalização de Knuth do algoritmo de Dijkstra para encontrar o menor caminho pode ser aplicada a uma gramática de árvore regular para computar, para cada não-terminal, o peso mínimo da sua árvore de derivação: Knuth, D.E. (1977). «A Generalization of Dijkstra's Algorithm». Information Processing Letters. 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3 . Baseado nessa informação, é fácil enumerar suas linguagens em ordem de peso crescente. Em particular, qualquer não-terminal com um peso mínimo infinito produz a linguagem vazia.
• Autômatos de árvores regulares tem sido generalizados para admitir testes de equivalência entre nós irmãos em árvores: Bogaert, B.; Tison, Sophie (1992). «Equality and Disequality Constraints on Direct Subterms in Tree Automata». Proc. 9th STACS. LNCS. 577. Springer. pp. 161–172 
• Permitir teste de equivalência entre nós mais profundos levam a indecidibilidade: Tommasi, M. (1991), Automates d'Arbres avec Tests d'Égalités entre Cousins Germains, LIFL-IT 

Ligações externas

• Técnicas de Autómatos de árvores e Aplicações