# 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$_1$∈ T$_Σ$(N) pode ser derivada em um único passo numa árvore t$_2$ ∈ T$_Σ$(N) (resumindo: t$_1$ ⇒$_G$ t$_2$), se existe um contexto S e uma produção (A→t) ∈ P como no exemplo:
* t$_1$ = S[A], e
* t$_2$ = 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

Seja G$_1$ = (N$_1$,Σ$_1$,Z$_1$,P$_1$), onde
* N$_1$ = {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),
* Z$_1$ = BList é o nosso não-terminal inicial, e
* o conjunto P$_1$ consiste nas seguintes produções:
** Bool → false
** Bool → true
** BList → nil
** BList → cons(Bool,BList)
Um exemplo de derivação da gramática G$_1$ é
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$_1$ é o conjunto de todas as listas finitas de valores booleanos L(G$_1$), que é igual a T$_{Σ1}$. A gramática G$_1$ corresponde a declaração de tipos algébricos
na linguagem de programação Standard ML: todos os membros de L(G$_1$) correspondem a um valor do tipo BList em Standard ML.
Em outro exemplo, seja G$_2$ = (N$_1$,Σ$_1$,BList1,P$_1$ ∪ P$_2$), usando o conjunto de não-terminais e o alfabeto definidos no exemplo anterior, mas estendendo o conjunto de produções anterior com P$_2$, consistindo das seguintes produções:
* BList1 → cons(true,BList)
* BList1 → cons(false,BList1)
A linguagem L(G$_2$) é o conjunto de todas as listas finitas de valores booleanos que contém true em pelo menos um item. O conjunto L(G$_2$) não possui tipo de dado equivalente em Standard ML, nem em nenhuma outra linguagem funcional. Ele um conjunto próprio de L(G$_1$). O termo do exemplo acima por acaso está em L(G$_2$), 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$_1$, L$_2$ são linguagens de árvores regulares, então os conjuntos de árvores L$_1$ ∩ L$_2$, L$_1$ ∪ L$_2$, e L$_1$ \ L$_2$ também são linguagens de árvores regulares, e é decidível tanto para L$_1$ ⊆ L$_2$, quanto para L$_1$ = L$_2$.

## 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.