Mostrar código-fonte de Gramática de Cabeça

'''Gramática de Cabeça''' (GC) é um formalismo gramatical introduzido por [[Carl Pollard]] (1984)<ref name="pollard1984">[[Carl Pollard|Pollard, C.]] 1984. ''Generalized Phrase Structure Grammars, Head Grammars, and Natural Language''. Ph.D. thesis, Stanford University, CA.</ref> como uma extensão da classe das [[Gramáticas Livres do Contexto]]. Gramática de Cabeça é então um tipo de [[gramática de estrutura frasal]], oposto a [[gramáticas de dependência]]. A classe das gramáticas de cabeça é um subconjunto das [[Gramática livre do contexto generalizada|Gramáticas livres do contexto generalizadas]].

Uma forma típica de definir gramáticas de cabeça é trocar as cadeias terminais de [[Gramáticas Livres do Contexto]] por cadeias terminais indexadas, onde o índice denota a palavra "cabeça" da cadeia. Assim, por exemplo, uma regra livre do contexto como <math>A \to abc</math> pode ser, ao invés, <math>A \to (abc, 0)</math>, onde o terminal 0, o "a", é a cabeça da cadeia terminal restante. Para conveniência de notação, tal regra poderia ser escrita apenas como a cadeia terminal, com o terminal cabeça denotado com alguma marca, como em <math>A \to \widehat{a}bc</math>.

Duas operações fundamentais são então adicionadas a todas as regras de reescrita: empacotamento e concatenação.

== Operações em cadeias encabeçadas ==
=== Empacotamento ===

Empacotamento é uma operação em duas cadeias encabeçadas definidas da seguinte forma:

Sejam <math>\alpha \widehat{x} \beta</math> e <math>\gamma \widehat{y} \delta</math> cadeias terminais encabeçadas por  ''x'' and ''y'', respectivamente.

<math>w(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta) = \alpha x \gamma \widehat{y} \delta \beta</math>

=== Concatenação ===

Concatenação é a família de operações em n > 0 cadeias, definida para n = 1, 2, 3 como segue:

Sejam <math>\alpha \widehat{x} \beta</math>, <math>\gamma \widehat{y} \delta</math>, e <math>\zeta \widehat{z} \eta</math> cadeias terminais encabeçadas por ''x'', ''y'', e ''z'', respectivamente.

<math>c_{1,0}(\alpha \widehat{x} \beta) = \alpha \widehat{x} \beta</math>

<math>c_{2,0}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta) = \alpha \widehat{x} \beta \gamma y \delta</math>

<math>c_{2,1}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta) = \alpha x \beta \gamma \widehat{y} \delta</math>

<math>c_{3,0}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta, \zeta \widehat{z} \eta) = \alpha \widehat{x} \beta \gamma y \delta \zeta z \eta</math>

<math>c_{3,1}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta, \zeta \widehat{z} \eta) = \alpha x \beta \gamma \widehat{y} \delta \zeta z \eta</math>

<math>c_{3,2}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta, \zeta \widehat{z} \eta) = \alpha x \beta \gamma y \delta \zeta \widehat{z} \eta</math>

E assim sucessivamente para  <math>c_{m,n} : 0 \leq n < m</math>. É possível obter o padrão simplesmente como "concatenar algum número de cadeias terminais 'm' com a cabeça de cadeia 'n', designada como a cabeça da cadeia resultante".

=== Forma das regras ===

Regras nas Gramáticas de Cabeça são definidas em termos dessas duas operações, com regras em um dos formatos

<math>X \to w(\alpha, \beta)</math>

<math>X \to c_{m,n}(\alpha, \beta, ...)</math>

onde <math>\alpha</math>, <math>\beta</math>, ... são cada uma um símbolo terminal ou um símbolo não terminal.

==Examplo==

Gramáticas de Cabeça são capazes de gerar a linguagem <math>\{ a^n b^n c^n d^n : n \geq 0 \}</math>. Nós podemos definir a gramática assim:

<math>S \to c_{1,0}(\widehat{\epsilon})</math>

<math>S \to c_{3,1}(\widehat{a}, T, \widehat{d})</math>

<math>T \to w(S, \widehat{b}c)</math>

A derivação para "abcd" é, então:

<math>S</math>

<math>c_{3,1}(\widehat{a}, T, \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(S, \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(c_{1,0}(\widehat{\epsilon}), \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(\widehat{\epsilon}, \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, \widehat{b}c, \widehat{d})</math>

<math>a\widehat{b}cd</math>

E para "aabbccdd":

<math>S</math>

<math>c_{3,1}(\widehat{a}, T, \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(S, \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, T, \widehat{d}), \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, w(S, \widehat{b}c), \widehat{d}), \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, w(c_{1,0}(\widehat{\epsilon}), \widehat{b}c), \widehat{d}), \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, w(\widehat{\epsilon}, \widehat{b}c), \widehat{d}), \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, \widehat{b}c, \widehat{d}), \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, w(a\widehat{b}cd, \widehat{b}c), \widehat{d})</math>

<math>c_{3,1}(\widehat{a}, ab\widehat{b}ccd, \widehat{d})</math>

<math>aab\widehat{b}ccdd</math>

==Propriedades formais==

===Equivalências===
Vijay-Shanker e Weir (1994)<ref name="vijayshankarAndWeir1994">Vijay-Shanker, K. and Weir, David J. 1994. ''The Equivalence of Four Extensions of Context-Free Grammars''. Mathematical Systems Theory 27(6): 511-546.</ref> demonstra que [[Gramáticas Lineares Indexadas]], [[Gramáticas Categóricas Combinatórias]], [[Gramática contígua de árvore]], e Gramáticas de Cabeça são formalismos fracamente equivalentes, de maneira que eles todos definem as mesmas linguagens de cadeias.

{{referências}}

[[Categoria:Linguagens formais]]
[[Categoria:Sintaxe]]