Gramática de Cabeça

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Gramática de Cabeça (GC) é um formalismo gramatical introduzido por Carl Pollard (1984)1 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 re-escrita: empacotamento e concatenação.

Operações em Cadeias Encabeçadas[editar | editar código-fonte]

Empacotamento[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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.

Example[editar | editar código-fonte]

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[editar | editar código-fonte]

Equivalências[editar | editar código-fonte]

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

References[editar | editar código-fonte]

  1. Pollard, C. 1984. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language. Ph.D. thesis, Stanford University, CA.
  2. Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars. Mathematical Systems Theory 27(6): 511-546.