Gramática de la cabeza

Concepto en contexto generalizado gramática libre

La gramática de cabeza ( HG ) es un formalismo gramatical introducido por Carl Pollard (1984) ^[1] como una extensión de la clase de gramáticas libres de contexto . Por lo tanto, la gramática de cabeza es un tipo de gramática de estructura de frase , a diferencia de una gramática de dependencia . La clase de gramáticas de cabeza es un subconjunto de los sistemas de reescritura lineales libres de contexto .

Una forma típica de definir gramáticas de cabeza es reemplazar las cadenas terminales de las CFG con cadenas terminales indexadas, donde el índice denota la palabra "cabeza" de la cadena. Así, por ejemplo, una regla CF como podría ser en cambio , donde el terminal 0, el a , es la cabeza de la cadena terminal resultante. Para facilitar la notación, una regla de este tipo podría escribirse simplemente como la cadena terminal, con la terminal de cabeza denotada por algún tipo de marca, como en . ${\displaystyle A\to abc}$ ${\displaystyle A\to (abc,0)}$ ${\displaystyle A\to {\widehat {a}}bc}$

Luego se agregan dos operaciones fundamentales a todas las reglas de reescritura: envoltura y concatenación.

Operaciones sobre cuerdas con cabeza

Envase

El ajuste es una operación sobre cadenas con dos encabezados definida de la siguiente manera:

Sean y cadenas terminales encabezadas por x e y , respectivamente. ${\displaystyle \alpha {\widehat {x}}\beta }$ ${\displaystyle \gamma {\widehat {y}}\delta }$

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

Concatenación

La concatenación es una familia de operaciones sobre cadenas con n > 0 encabezados, definidas para n = 1, 2, 3 de la siguiente manera:

Sean , , y cadenas terminales encabezadas por x , y , y z , respectivamente. ${\displaystyle \alpha {\widehat {x}}\beta }$ ${\displaystyle \gamma {\widehat {y}}\delta }$ ${\displaystyle \zeta {\widehat {z}}\eta }$

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

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

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

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

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

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

Y así sucesivamente para . Se puede resumir el patrón aquí simplemente como "concatenar una cierta cantidad de cadenas terminales m , con la cabeza de la cadena n designada como la cabeza de la cadena resultante". ${\displaystyle c_{m,n}:0\leq n<m}$

Forma de reglas

Las reglas gramaticales principales se definen en términos de estas dos operaciones, y las reglas adoptan cualquiera de las formas

${\displaystyle X\to w(\alpha ,\beta )}$

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

donde , , ... son cada uno una cadena terminal o un símbolo no terminal. ${\displaystyle \alpha }$ ${\displaystyle \beta }$

Ejemplo

Las gramáticas de cabeza son capaces de generar el lenguaje . Podemos definir la gramática de la siguiente manera: ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}:n\geq 0\}}$

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

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

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

La derivación de "abcd" es así:

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

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

Y 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(a{\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}$

Propiedades formales

Equivalencias

Vijay-Shanker y Weir (1994) ^[2] demuestran que las gramáticas indexadas lineales , la gramática categorial combinatoria , las gramáticas contiguas a árboles y las gramáticas principales son formalismos débilmente equivalentes , ya que todas definen los mismos lenguajes de cadenas.

Referencias

1. Pollard, C. 1984. Gramáticas de estructura de frase generalizada, gramáticas principales y lenguaje natural . Tesis de doctorado, Universidad de Stanford, CA.
2. Vijay-Shanker, K. y Weir, David J. 1994. La equivalencia de cuatro extensiones de gramáticas libres de contexto . Teoría de sistemas matemáticos 27(6): 511-546.