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 t1∈ TΣ(N) pode ser derivada em um único passo numa árvore t2 ∈ TΣ(N) (resumindo: t1 ⇒G t2), se existe um contexto S e uma produção (A→t) ∈ P como no exemplo:

t1 = S[A], e t2 = 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

upright=2.5|thumb|Exemplo árvore de derivação G1 em notação linear (tabela no canto superior esquerdo) e gráfica (figura principal)

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

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

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 G1 é o conjunto de todas as listas finitas de valores booleanos L(G1), que é igual a TΣ1. A gramática G1 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(G1) correspondem a um valor do tipo BList em Standard ML.

Em outro exemplo, seja G2 = (N1,Σ1,BList1,P1 ∪ P2), usando o conjunto de não-terminais e o alfabeto definidos no exemplo anterior, mas estendendo o conjunto de produções anterior com P2, consistindo das seguintes produções: BList1 → cons(true,BList) BList1 → cons(false,BList1) A linguagem L(G2) é o conjunto de todas as listas finitas de valores booleanos que contém true em pelo menos um item. O conjunto L(G2) não possui tipo de dado equivalente em Standard ML, nem em nenhuma outra linguagem funcional. Ele um conjunto próprio de L(G1). O termo do exemplo acima por acaso está em L(G2), 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 L1, L2 são linguagens de árvores regulares, então os conjuntos de árvores L1 ∩ L2, L1 ∪ L2, e L1 \ L2 também são linguagens de árvores regulares, e é decidível tanto para L1 ⊆ L2, quanto para L1 = L2.

Caracterizações adicionais e relações com outras linguagens formais Rajeev Alur e Parthasarathy Madhusudan Sect.4, Theorem 5. Sect.7 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ãoComon et al, Tree Automata Techniques and Applications, 1997 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: Gramáticas de árvores regulares já haviam sido descritas em 1968 por:

As aplicações de gramáticas de árvores regulares incluem: Seleção de Instruções em geração de código de compiladores: 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: Resolver cláusulas sobre conjuntos: 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: Algoritmos sobre gramáticas de árvore regular são discutidos a partir de uma visão orientada pela eficiência em: 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: . 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: Permitir teste de equivalência entre nós mais profundos levam a indecidibilidade:

Referências

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

Categoria:Linguagens formais