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(\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 {})$ $\Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon$