Gramática de Cabeça

Gramática de Cabeça (GC) é um formalismo gramatical introduzido por Carl Pollard (1984) 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á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 $A\to abc$ pode ser, ao invés, $A\to (abc,0)$, 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 $A\to {\widehat {a}}bc$.

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 $\alpha {\widehat {x}}\beta$ e $\gamma {\widehat {y}}\delta$ cadeias terminais encabeçadas por x and y, respectivamente.

$w(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\gamma {\widehat {y}}\delta \beta$

Concatenação

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

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

$c_{1,0}(\alpha {\widehat {x}}\beta )=\alpha {\widehat {x}}\beta$

$c_{2,0}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha {\widehat {x}}\beta \gamma y\delta$

$c_{2,1}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\beta \gamma {\widehat {y}}\delta$

$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$

$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$

$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$

E assim sucessivamente para $c_{m,n}:0\leq n<m$. É 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

$X\to w(\alpha ,\beta )$

$X\to c_{m,n}(\alpha ,\beta ,...)$

onde $\alpha$, $\beta$, ... 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 $\{a^{n}b^{n}c^{n}d^{n}:n\geq 0\}$. Nós podemos definir a gramática assim:

$S\to c_{1,0}({\widehat {\epsilon }})$

$S\to c_{3,1}({\widehat {a}},T,{\widehat {d}})$

$T\to w(S,{\widehat {b}}c)$

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

$S$

$c_{3,1}({\widehat {a}},T,{\widehat {d}})$

$c_{3,1}({\widehat {a}},w(S,{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},w(c_{1,0}({\widehat {\epsilon }}),{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},w({\widehat {\epsilon }},{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},{\widehat {b}}c,{\widehat {d}})$

$a{\widehat {b}}cd$

E para "aabbccdd":

$S$

$c_{3,1}({\widehat {a}},T,{\widehat {d}})$

$c_{3,1}({\widehat {a}},w(S,{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},T,{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},w(S,{\widehat {b}}c),{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})$

$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}})$

$c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},w({\widehat {\epsilon }},{\widehat {b}}c),{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},{\widehat {b}}c,{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},w(a{\widehat {b}}cd,{\widehat {b}}c),{\widehat {d}})$

$c_{3,1}({\widehat {a}},ab{\widehat {b}}ccd,{\widehat {d}})$

$aab{\widehat {b}}ccdd$

Propriedades formais

Equivalências

Vijay-Shanker e Weir (1994) 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.