Gramática libre de contexto generalizada

La gramática libre de contexto generalizada (GCFG) es un formalismo gramatical que amplía las gramáticas libres de contexto añadiendo funciones de composición potencialmente no libres de contexto a las reglas de reescritura. ^{[ 1 ]} La gramática de cabeza (y sus equivalentes débiles) es un ejemplo de dicha GCFG que se sabe que es especialmente hábil para manejar una amplia variedad de propiedades no libres de contexto del lenguaje natural.

Una 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${\displaystyle f(\langle x_{1},...,x_{m}\rangle ,\langle y_{1},...,y_{n}\rangle ,...)=\gamma }$, dónde${\displaystyle \gamma }$es o bien una tupla de cadena única, o bien el uso de una función de composición (potencialmente diferente) que se reduce a una tupla de cadena. Las reglas de reescritura se ven así:${\displaystyle X\to f(Y,Z,...)}$, dónde${\displaystyle Y}$,${\displaystyle Z}$, ... son tuplas de cadenas o símbolos no terminales.

La semántica de reescritura de las 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 composiciones (funciones de composición aplicadas a tuplas de cadenas u otras composiciones). A continuación, se aplican las funciones de composición, reduciendo sucesivamente las tuplas a una sola.

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

La producción de CF de abbbba es

S

aSa

abSba

abbSbba

abbba

y la producción de GCFG correspondiente es

${\displaystyle S\to conc(\langle a\rangle ,S,\langle a\rangle )}$

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle a\rangle )}$

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}$

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle ),\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}$

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,\langle \epsilon \rangle ,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}$

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,\langle bb\rangle ,\langle b\rangle ),\langle a\rangle )}$

${\displaystyle conc(\langle a\rangle ,\langle bbbb\rangle ,\langle a\rangle )}$

${\displaystyle \langle abbbba\rangle }$

Weir (1988) ^{[ 1 ]} describe dos propiedades de las funciones de composición: linealidad y regularidad. Una función definida como${\displaystyle f(x_{1},...,x_{n})=...}$es lineal si y solo si cada variable aparece como máximo una vez a cada lado del = , haciendo que${\displaystyle f(x)=g(x,y)}$lineal pero no${\displaystyle f(x)=g(x,x)}$. Una función definida como${\displaystyle f(x_{1},...,x_{n})=...}$es regular si el lado izquierdo y el lado derecho tienen exactamente las mismas variables, lo que hace que sea regular si el lado izquierdo y el lado derecho tienen exactamente las mismas variables.${\displaystyle f(x,y)=g(y,x)}$regular pero no${\displaystyle f(x)=g(x,y)}$o${\displaystyle f(x,y)=g(x)}$.

Una gramática en la que todas las funciones de composición son lineales y regulares se denomina Sistema de Reescritura Libre de Contexto Lineal (LCFRS). El LCFRS es una subclase propia de las GCFG, es decir, tiene una capacidad computacional estrictamente menor que las GCFG en su conjunto.

Por otro lado, las LCFRS son estrictamente más expresivas que las gramáticas indexadas linealmente y sus gramáticas adjuntivas de árboles variantes débilmente equivalentes (TAG). ^{[ 2 ]} La gramática de cabeza es otro ejemplo de una LCFRS que es estrictamente menos potente que la clase de LCFRS en su conjunto.

LCFRS son débilmente equivalentes a TAGs multicomponentes (locales de conjuntos) ( MCTAGs ) y también a gramáticas libres de contexto múltiples (MCFGs).). ^{[ 3 ]} y gramáticas minimalistas (MG). Los lenguajes generados por LCFRS (y sus equivalentes débiles) pueden ser analizados en tiempo polinomial . ^{[ 4 ]}

• gramática de concatenación de rangos