Gramática de movimento literal

Gramáticas de movimento literal (LMGs do inglês Literal movement grammar) vem de um formalismo introduzido por Groenink em 1995. Destina-se a caracterização de fênomenos de extraposição da linguagem natural, como topicalização e cross-serial. LMGs estendem da classe das gramáticas livres de contexto (GLCs), introduzido semântica reescrita na forma de função de correspondência de padrões, bem como operações de união e eliminação de uma variável.

Descrição[editar | editar código-fonte]

A operação de escrita de uma LMG é muito semelhante a de uma GLC, com a adição de "argumentos" para os símbolos não-terminais. Enquanto a gramática livre de contexto obedece como regra geral S → α, ou seja, cada não terminal S gera algum terminal α ou uma nova variável com um terminal, uma regra LMG obedece o esquema geral X(x₁,...,x_n) → α onde X é um não terminal de aridade n (chamado de predicado na terminologia do LMG), e α é uma palavra de “itens” (definido posteriormente). Os argumentos xi são sequências de símbolos terminais e/ou variáveis que definem o padrão. No caso em que um padrão possui múltiplas variáveis de adjacências, corresponderá a quaisquer partições de mesmo valor. Assim, se o predicado é f (x, y) e o padrão real é f (ab), há três resultados válidos: x = ε, y = ab; x = a, y = b; x = ab, y = ε. Desta forma uma única regra é um conjunto de possibilidades. Um “item” em gramática de momvimento literal é da forma

${\textstyle f(x1,...,xn)}$ , um predicado de aridade n
${\textstyle x:f(x1,...,xn)}$ , uma variável x ligada com a palavra produzida por ${\textstyle f(x1,...,xn)}$
$f(x1,...,xn)/a$ , uma remoção de ${\textstyle f(x1,...,xn)}$ por uma palavra de terminais/ou variáveis a

Em uma regra onde f(x1,...,xm) → α y:g(z1,...,zn)β, a variável y é ligada com qualquer símbolo terminal produzido pelo predicado g, e em α e β, todas as ocorrências de y são substituídas por palavras, e em α e β são produzidas como se símbolos terminais ali estivessem. Um item $x/y$ , onde x é algo que produz uma string terminal (tanto por ela mesma como por algum predicado), e y é uma palavra de terminais e/ou variáveis, é escrita como uma palavra vazia (ε) se e somente se ${\textstyle g(y1,...,yn)}$ , caso contrário, não pode ser escrita.

Exemplo[editar | editar código-fonte]

LMGs são caracterizadas de linguagens, não-livre de contexto ${\textstyle a^{n}b^{n}c^{n}:n>=1}$ como segue:

   S() → x: A() B(x)
   S() → a A()
   A() → ε
   B(xy) → a/x b B(y)c
   B(ε) → ε

A derivação para aabbcc, usando parêntesis para indicar agrupamento é

   S() → x:A() B(x) → x:(a A()) B(x) → x:(aa A()) B(x) → x:aa B(x) → aa B(aa)
   → aa a/a b B(a) c → aab B(a) c → aab a/a b B() cc → aabb B() cc → aabbcc

Descrição[editar | editar código-fonte]

A operação de escrita de uma LMG é muito semelhante a de uma GLC, com a adição de "argumentos" para os símbolos não-terminais. Enquanto a gramática livre de contexto obedece como regra geral S → α, ou seja, cada não terminal S gera algum terminal α ou uma nova variável com um terminal, uma regra LMG obedece o esquema geral X(x₁,...,x_n) → α onde X é um não terminal de aridade n (chamado de predicado na terminologia do LMG), e α é uma palavra de “itens” (definido posteriormente). Os argumentos xi são sequências de símbolos terminais e/ou variáveis que definem o padrão. No caso em que um padrão possui múltiplas variáveis de adjacências, corresponderá a quaisquer partições de mesmo valor. Assim, se o predicado é f (x, y) e o padrão real é f (ab), há três resultados válidos:

Poder Computacional[editar | editar código-fonte]

Linguagens geradas por esta gramática contem as linguagens livres de contexto como subconjunto, como cada CFG é um LMG, onde todos os predicados têm aridade 0 e nenhuma regra de produção contém ligações entre variáveis ou exclusões.

Referências

Groenink, Annius V. 1995. Literal Movement Grammars. In Proceedings of the 7th EACL Conference.