# Gramática de concatenação de intervalo

Gramática de concatenação de intervalo, em tradução livre de range concatenation grammar (RCG), é uma gramática formal desenvolvida por Pierre Boullier em 1998 como uma tentativa de representar uma série de fenômenos da linguagem natural, como os números chineses e embaralhamento de palavras alemãs, que não pertencem às linguagens moderadamente sensíveis ao contexto (tradução livre de Mildly context-sensitive languages).
De um ponto de vista teórico, qualquer linguagem pode ser analisada em tempo polinomial se, e somente se, pertencer ao subconjunto de RCG chamado gramáticas de Concatenação de Intervalo Positivo (tradução livre de positive range concatenation grammars).
Embora projetada como uma variante das Gramáticas de Movimento Literal de Groenink (sigla LMG), as RCGs tratam o processo gramático mais como prova do que produção. Enquanto LMGs produzem uma cadeia final de um predicado inicial, RCGs focam em reduzir o predicado inicial (que implica na cadeia final) para a cadeia vazia, que constitui a prova do pertencimento da cadeia final à linguagem.

## Descrição
### Definição Formal

Uma gramática de Concatenação de Intervalo Positivo - tradução livre de positive range concatenation grammar, PRCG - é uma tupla $G=(N,~T,~V,~S,~P)$, onde:
* $N$, $T$ e $V$ são conjuntos disjuntos finitos de (respectivamente) predicados, simbolos teminais e variáveis. Cada nome de predicado tem uma aridade associada dada pela função $dim:N\rightarrow \mathbb {N} \setminus \{0\}$.
* $S\in N$ é o início do predicado e verifica $dim(S)=1$.
* $P$ é um conjunto finito de cláusulas da forma $\psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}$, onde os $\psi _{i}$ são predicados da forma $A_{i}(\alpha _{1},\ldots ,\alpha _{dim(A_{i})})$ com $A_{i}\in N$ e $\alpha _{i}\in (T\cup V)^{\star }$.
Uma gramática de Concatenação de Intervalo Negativo - tradução livre de Negative Range Concatenation Grammar, NRCG - é definida como uma PRCG, mas com o adicional de que alguns predicados ocorrendo no lado direito das cláusulas podem ter a forma ${\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{dim(A_{i})})}}$. Estes predicados são chamados predicados negativos.
Uma gramática de Concatenação de Intervalo é ou positiva ou negativa. Embora PRCGs sejam tecnicamente NRCGs, dizemos que essas gramáticas são de intervalos negativos ou positivos enfatizar a ausência ou presença de predicados negativos.
Um intervalo no palavra $w\in T^{\star }$ são alguns $\langle l,r\rangle _{w}$, com $0\leq l\leq r\leq n$, onde $n$ é o comprimento de $w$. Dois intervalos $\langle l_{1},r_{1}\rangle _{w}$ and $\langle l_{2},r_{2}\rangle _{w}$ podem ser concatenados sse $r_{1}=l_{2}$, então nós temos: $\langle l_{1},r_{1}\rangle _{w}\cdot \langle l_{2},r_{2}\rangle _{w}=\langle l_{1},r_{2}\rangle _{w}$.
Para uma palavra $w=w_{1}w_{2}\ldots w_{n}$, com $w_{i}\in T$, a notação pontuada para intervalos é: $\langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{r-1}\bullet w_{r}\ldots w_{n}$.

### Reconhecimento de cadeias

Como LMGs, cláusulas de RCG tem o esquema geral $A(x_{1},...,x_{n})\to \alpha$, onde em uma RCG, $\alpha$ é, ou a cadeia vazia ou uma cadeia de predicados. Os argumentos $x_{i}$ consistem de cadeias de símbolos terminais e/ou símbolos de variáveis, padrão o qual corresponde com os valores do argumento atual como no LMG. Variáveis adjascentes constituem uma família de correspondências em partições, então esse argumento $xy$, onde duas variáveis, correnpondem a cadeias de litais $ab$ em três modos diferentes: $x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon$.
Termos predicados vêm de duas formas, positiva (que produz a cadeia vazia em caso de sucesso), e negativa (que produz a cadeia vazia em caso de falha ou se termos positivos não produzem a cadeia vazia). Termos negativos são denotados da mesma forma que os positivos, com uma barra sob si, como em ${\overline {A(x_{1},...,x_{n})}}$.
A re-escrita da semântica para RCGs é bastante simples, idêntica à semântica correspondente de LMGs. Dado uma cadeia de predicado $A(\alpha _{1},...,\alpha _{n})$, onde os símbolos $\alpha _{i}$ são cadeias finais, se há uma regra $A(x_{1},...,x_{n})\to \beta$ na gramática que corresponde à cadeia de predicado , a cadeia de predicado é substituida por $\beta$, substituindo as variáveis correspondentes em cada $x_{i}$.
Por exemplo, dada uma regra $A(x,ayb)\to B(axb,y)$, onde $x$ and $y$ são símbolos de variáveis e $a$ e $b$ são símbolos terminais, a cadeia de predicado $A(a,abb)$ pode ser re-escrita como $B(aab,b)$, porque $A(a,abb)$ corresponde a $A(x,ayb)$ onde $x=a,\ y=b$. Da mesma forma, se houvesse uma regra $A(x,ayb)\to A(x,x)\ A(y,y)$, $A(a,abb)$ poderiamos re-escrever como $A(a,a)\ A(b,b)$.
A prova/reconhecimento de uma cadeia $\alpha$ é feita mostrando que $S(\alpha )$ produz a cadeias vazia. Para os passos de re-escrita individuais, quando multiplas correspondecias alternativas de variáveis são possíveis, qualquer re-escrita que pode guiar a prova por inteiro é considerada.

## Exemplo

RCGs são capazes de reconhecer uma linguagem de índice não-linear $\{www:w\in \{a,b\}^{*}\}$ como segue:
Sejam x, y, and z símbolos de variáveis:
$S(xyz)\to A(x,y,z)$
$A(ax,ay,az)\to A(x,y,z)$
$A(bx,by,bz)\to A(x,y,z)$
$A(\epsilon ,\epsilon ,\epsilon )\to \epsilon$
A prova para abbabbabb é então
$S(abbabbabb)\Rightarrow A(abb,abb,abb)\Rightarrow A(bb,bb,bb)\Rightarrow A(b,b,b)\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon$
Ou, usando a mais correta "notação pontuada" para intervalos:
$S(\bulletabbabbabb\bullet)\Rightarrow A(\bulletabb\bulletabbabb,abb\bulletabb\bulletabb,abbabb\bulletabb\bullet)\Rightarrow A(a\bulletbb\bulletabbabb,abba\bulletbb\bulletabb,abbabba\bulletbb\bullet)$ $\Rightarrow A(ab\bulletb\bulletabbabb,abbab\bulletb\bulletabb,abbabbab\bulletb\bullet)\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon$

## References

* ↑ Pierre Boullier (1998). «Chinese Numbers, MIX, Scrambling, and Range Concatenation Grammars». Proposal for a Natural Language Processing Syntactic Backbone (PDF). [S.l.: s.n.]
* ↑ Pierre Boullier (1999). «Chinese Numbers, MIX, Scrambling, and Range Concatenation Grammars». Proc. EACL (PDF). [S.l.: s.n.] pp. 53–60. Consultado em 17 de fevereiro de 2015. Arquivado do original (PDF) em 15 de maio de 2003
* ↑ Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. [S.l.]: Springer Science & Business Media. p. 37. ISBN 978-3-642-14846-0 citing http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf
vdeInformática Teórica: linguagens formais and Gramáticas formais :
Hierarquia de ChomskyGramáticasLinguagensMáquinas abstratas
Tipo-0
Tipo-1
Tipo-2
Tipo-3
Irrestrita
(no common name)
Sensível ao contexto
Positiva Concatenação de intervalo$^*$
Indexada$^*$
Gramáticas Livres do Contexto Generalizadas
Árvore adjacente
Livre de contexto
Determinística livre de contexto
Palavra aninhada
Regular
Non-recursive
Recursivamente Enumerável
Decidível
Sensível ao contexto
Positiva Concatenação de intervalo
Indexada
en:Linear context-free rewriting language
Tree-adjoining
Livre de Contexto
Deterministic context-free
Palavra aninhada
Regular
Star-free
Finita
Máquina de Turing
Decisor
linear limitada
P (Complexidade) Máquina de Turing
Nested stack
en:Thread automaton
Automato com pilha embutido
Automato com pilha não-determinístico
Automato com pilha determinístico
palavra aninhada
Finito
Counter-free (with aperiodic finite monoid)
Acíclico finito :
Cada categoria das linguagens, exceto aquelas marcadas por um $^*$, é subconjunto próprio da categoria diretamente acima. Qualquer linguagem em cada categoria é gerada por uma gramática e por um autômato na categoria da mesma linha. :