Cabeça de gramática - Head grammar

Gramática cabeça ( HG ) é um formalismo gramática introduzido em Carl Pollard (1984) como uma extensão da gramática livre de contexto classe de gramáticas. Cabeça gramática é, portanto, um tipo de frase estrutura secundária , em oposição a uma gramática de dependência . A classe de gramáticas cabeça é um subconjunto dos sistemas de reescrita livres de contexto lineares .

Uma forma típica de definir cabeça gramáticas é substituir as cordas terminais de CFGs com cordas terminais indexados, onde o índice denota a palavra "cabeça" da cadeia. Assim, por exemplo, uma regra de CF tal como pode em vez disso ser , onde o terminal 0, a um , é a cabeça do terminal de cadeia resultante. Por conveniência de notação, tal regra poderia ser escrito como apenas a string terminal, com o terminal de cabeça denotado por algum tipo de marca, como em . ${\ Displaystyle A \ to abc}$${\ Displaystyle A \ a (ABC, 0)}$${\ Displaystyle A \ a {\ widehat {a}}} bc$

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

Operações com strings dirigidos

Invólucro

Embrulho é uma operação em duas cordas dirigidos definidos como se segue:

Deixe e ser cadeias terminais encabeçados por x e y , respectivamente. ${\ Displaystyle \ alfa {\ widehat {x}} \ beta}$${\ Displaystyle \ gama {\ widehat {y}} \ delta}$

${\ Displaystyle w (\ alfa {\ widehat {x}} \ beta, \ gama {\ widehat {y}} \ delta) = \ alfa x \ gama {\ widehat {y}} \ delta beta \}$

Concatenação

A concatenação é uma família de operações em n> 0 dirigido cordas, definido por n = 1, 2, 3 como se segue:

Vamos , e ser cadeias terminais encabeçados por x , y , e z , respectivamente. ${\ Displaystyle \ alfa {\ widehat {x}} \ beta}$${\ Displaystyle \ gama {\ widehat {y}} \ delta}$${\ Displaystyle \ zeta {\ widehat {z}} \ eta}$

${\ Displaystyle C_ {1,0} (\ alfa {\ widehat {x}} \ beta) = \ alfa {\ widehat {x}} \ beta}$

${\ Displaystyle C_ {2,0} (\ alfa {\ widehat {x}} \ beta, \ gama {\ widehat {y}} \ delta) = \ alfa {\ widehat {x}} \ beta \ gama y \ delta}$

${\ Displaystyle C_ {2,1} (\ alfa {\ widehat {x}} \ beta, \ gama {\ widehat {y}} \ delta) = \ alfa x \ beta \ gama {\ widehat {y}} \ delta}$

${\ Displaystyle C_ {3,0} (\ alfa {\ widehat {x}} \ beta, \ gama {\ widehat {y}} \ delta, \ zeta {\ widehat {z}} \ eta) = \ alfa { \ widehat {x}} \ beta \ gama y \ delta \ zeta Z \ eta}$

${\ Displaystyle C_ {3,1} (\ alfa {\ widehat {x}} \ beta, \ gama {\ widehat {y}} \ delta, \ zeta {\ widehat {z}} \ eta) = \ x alfa \ beta \ gama {\ widehat {y}} \ delta \ zeta Z eta \}$

${\ Displaystyle C_ {3,2} (\ alfa {\ widehat {x}} \ beta, \ gama {\ widehat {y}} \ delta, \ zeta {\ widehat {z}} \ eta) = \ x alfa \ beta \ gama y \ delta \ zeta {\ widehat {z}} \ eta}$

E assim por diante para . Pode-se resumir o padrão aqui simplesmente como "concatenar algum número de terminais cordas m , com a cabeça de cordas n designado como o chefe da cadeia resultante". ${\ Displaystyle C_ {m, n}: 0 \ leq n <m}$

Forma de regras

regras gramaticais cabeça são definidas em termos dessas duas operações, com regras de tomar qualquer das formas

${\ Displaystyle X \ a w (\ alfa, \ beta)}$

${\ Displaystyle X \ a C_ {m, n} (\ alfa, \ beta, ...)}$

onde , ... são cada um uma cadeia terminal ou um símbolo não-terminal. ${\ Displaystyle \ alfa}$${\ Displaystyle \ beta}$

Exemplo

Gramáticas cabeça são capazes de gerar a linguagem . Podemos definir a gramática da seguinte forma: ${\ Displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n}: n \ GEQ 0 \}}$

${\ Displaystyle \ S para C_ {1,0} ({\ widehat {\ epsilon}})}$

${\ Displaystyle \ S para C_ {3,1} ({\ widehat {a}}, t, {\ widehat {d}})}$

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

A derivação de "abcd" é assim:

${\ Displaystyle S}$

${\ Displaystyle C_ {3,1} ({\ widehat {a}}, t, {\ widehat {d}})}$

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

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

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

${\ Displaystyle C_ {3,1} ({\ widehat {a}}, {\ widehat {b}} C, {\ widehat {d}})}$

${\ A {\ widehat {b}} cd displaystyle}$

E para "aabbccdd":

${\ Displaystyle S}$

${\ Displaystyle C_ {3,1} ({\ widehat {a}}, t, {\ widehat {d}})}$

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

${\ Displaystyle C_ {3,1} ({\ widehat {a}}, w (C_ {3,1} ({\ widehat {a}}, t, {\ widehat {d}}), {\ {widehat b}} c), {\ widehat {d}})}$

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

${\ Displaystyle 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}})}$

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

${\ Displaystyle C_ {3,1} ({\ widehat {a}}, w (C_ {3,1} ({\ widehat {a}}, {\ widehat {b}} C, {\ widehat {d} }), {\ widehat {b}} c), {\ widehat {d}})}$

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

${\ Displaystyle C_ {3,1} ({\ widehat {a}}, {ab \ widehat {b}} CCD, {\ widehat {d}})}$

${\ Displaystyle AAB {\ widehat {b}}} CCDD$

propriedades formais

equivalências

Vijay-Shanker e Weir (1994) demonstra que a gramática linear indexados , gramática combinatória categorial , gramáticas-contíguo de árvores e gramáticas de cabeça são fracamente equivalentes formalismos, em que todos eles definem os mesmos idiomas cordas.

Referências