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 pode ser, ao invés, , 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 .

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 e cadeias terminais encabeçadas por x and y, respectivamente.

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 , , e cadeias terminais encabeçadas por x, y, e z, respectivamente.

E assim sucessivamente para . É 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

onde , , ... 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 . Nós podemos definir a gramática assim:

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

E para "aabbccdd":

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.