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 ^[1] 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^[2]).

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).^[3]

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.

Uma gramática de Concatenação de Intervalo Positivo - tradução livre de positive range concatenation grammar, PRCG - é uma tupla ${\displaystyle G=(N,~T,~V,~S,~P)}$, onde:

• ${\displaystyle N}$, ${\displaystyle T}$ e ${\displaystyle 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 ${\displaystyle dim:N\rightarrow \mathbb {N} \setminus \{0\}}$.
• ${\displaystyle S\in N}$ é o início do predicado e verifica ${\displaystyle dim(S)=1}$.
• ${\displaystyle P}$ é um conjunto finito de cláusulas da forma ${\displaystyle \psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}}$, onde os ${\displaystyle \psi _{i}}$ são predicados da forma ${\displaystyle A_{i}(\alpha _{1},\ldots ,\alpha _{dim(A_{i})})}$ com ${\displaystyle A_{i}\in N}$ e ${\displaystyle \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 ${\displaystyle {\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 ${\displaystyle w\in T^{\star }}$ são alguns ${\displaystyle \langle l,r\rangle _{w}}$, com ${\displaystyle 0\leq l\leq r\leq n}$, onde ${\displaystyle n}$ é o comprimento de ${\displaystyle w}$. Dois intervalos ${\displaystyle \langle l_{1},r_{1}\rangle _{w}}$ and ${\displaystyle \langle l_{2},r_{2}\rangle _{w}}$ podem ser concatenados sse ${\displaystyle r_{1}=l_{2}}$, então nós temos: ${\displaystyle \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 ${\displaystyle w=w_{1}w_{2}\ldots w_{n}}$, com ${\displaystyle w_{i}\in T}$, a notação pontuada para intervalos é: ${\displaystyle \langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{r-1}\bullet w_{r}\ldots w_{n}}$.

Como LMGs, cláusulas de RCG tem o esquema geral ${\displaystyle A(x_{1},...,x_{n})\to \alpha }$, onde em uma RCG, ${\displaystyle \alpha }$ é, ou a cadeia vazia ou uma cadeia de predicados. Os argumentos ${\displaystyle 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 ${\displaystyle xy}$, onde duas variáveis, correnpondem a cadeias de litais ${\displaystyle ab}$ em três modos diferentes: ${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle A(\alpha _{1},...,\alpha _{n})}$, onde os símbolos ${\displaystyle \alpha _{i}}$ são cadeias finais, se há uma regra ${\displaystyle A(x_{1},...,x_{n})\to \beta }$ na gramática que corresponde à cadeia de predicado , a cadeia de predicado é substituida por ${\displaystyle \beta }$, substituindo as variáveis correspondentes em cada ${\displaystyle x_{i}}$.

Por exemplo, dada uma regra ${\displaystyle A(x,ayb)\to B(axb,y)}$, onde ${\displaystyle x}$ and ${\displaystyle y}$ são símbolos de variáveis e ${\displaystyle a}$ e ${\displaystyle b}$ são símbolos terminais, a cadeia de predicado ${\displaystyle A(a,abb)}$ pode ser re-escrita como ${\displaystyle B(aab,b)}$, porque ${\displaystyle A(a,abb)}$ corresponde a ${\displaystyle A(x,ayb)}$ onde ${\displaystyle x=a,\ y=b}$. Da mesma forma, se houvesse uma regra ${\displaystyle A(x,ayb)\to A(x,x)\ A(y,y)}$, ${\displaystyle A(a,abb)}$ poderiamos re-escrever como ${\displaystyle A(a,a)\ A(b,b)}$.

A prova/reconhecimento de uma cadeia ${\displaystyle \alpha }$ é feita mostrando que ${\displaystyle 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.

RCGs são capazes de reconhecer uma linguagem de índice não-linear ${\displaystyle \{www:w\in \{a,b\}^{*}\}}$ como segue:

Sejam x, y, and z símbolos de variáveis:

${\displaystyle S(xyz)\to A(x,y,z)}$

${\displaystyle A(ax,ay,az)\to A(x,y,z)}$

${\displaystyle A(bx,by,bz)\to A(x,y,z)}$

${\displaystyle A(\epsilon ,\epsilon ,\epsilon )\to \epsilon }$

A prova para abbabbabb é então

${\displaystyle 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:

${\displaystyle S(\bullet {}abbabbabb\bullet {})\Rightarrow A(\bullet {}abb\bullet {}abbabb,abb\bullet {}abb\bullet {}abb,abbabb\bullet {}abb\bullet {})\Rightarrow A(a\bullet {}bb\bullet {}abbabb,abba\bullet {}bb\bullet {}abb,abbabba\bullet {}bb\bullet {})}$ ${\displaystyle \Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$