Gramática generalizada libre de contexto

---

La gramática libre de contexto generalizada (GCFG) es un formalismo gramatical que amplía las gramáticas libres de contexto al agregar funciones de composición potencialmente libres de contexto para reescribir las reglas. ^[1] La gramática principal (y sus equivalentes débiles) es un ejemplo de tal GCFG que se sabe que es especialmente hábil en el manejo de una amplia variedad de propiedades del lenguaje natural que no son CF.

Un GCFG consta de dos componentes: un conjunto de funciones de composición que combinan tuplas de cadenas y un conjunto de reglas de reescritura. Todas las funciones de composición tienen la forma , donde hay una sola tupla de cadena o algún uso de una función de composición (potencialmente diferente) que se reduce a una tupla de cadena. Las reglas de reescritura se ven como , donde ,, ... son tuplas de cadenas o símbolos no terminales.${\ Displaystyle f (\ langle x_ {1}, ..., x_ {m} \ rangle, \ langle y_ {1}, ..., y_ {n} \ rangle, ...) = \ gamma}$${\ Displaystyle \ gamma}$${\ Displaystyle X \ af (Y, Z, ...)}$${\ Displaystyle Y}$${\ Displaystyle Z}$

La semántica de reescritura de los GCFG es bastante sencilla. Una aparición de un símbolo no terminal se reescribe utilizando reglas de reescritura como en una gramática libre de contexto, lo que finalmente produce solo composiciones (funciones de composición aplicadas a tuplas de cuerdas u otras composiciones). A continuación, se aplican las funciones de composición, reduciendo sucesivamente las tuplas a una única tupla.

Se puede realizar una traducción simple de una gramática libre de contexto a un GCFG de la siguiente manera. Dada la gramática en ( 1 ), que genera el lenguaje palíndromo , donde es la cadena inversa de , podemos definir la función de composición conc como en ( 2a ) y las reglas de reescritura como en ( 2b ).${\ Displaystyle \ {ww ^ {R}: w \ in \ {a, b \} ^ {*} \}}$${\ Displaystyle w ^ {R}}$${\ Displaystyle w}$

---