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.
Descripción
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, dónde es una tupla de una sola 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, dónde , , ... son tuplas de cadena o símbolos no terminales.
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.
Ejemplo
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, dónde 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 ).
( 1 )
( 2a )
( 2b )
La producción de CF de abbbba es
- S
- como un
- abSba
- abbSbba
- abbbba
y la producción correspondiente de GCFG es
Sistemas de reescritura lineal sin contexto (LCFRS)
Weir (1988) [1] describe dos propiedades de las funciones de composición, linealidad y regularidad. Una función definida comoes lineal si y solo si cada variable aparece como máximo una vez a cada lado de = , lo que hace lineal pero no . Una función definida como es regular si el lado izquierdo y el lado derecho tienen exactamente las mismas variables, lo que hace regular pero no o .
Una gramática en la que todas las funciones de composición son tanto lineales como regulares se denomina Sistema de reescritura lineal sin contexto (LCFRS). LCFRS es una subclase propia de los GCFG, es decir, tiene estrictamente menos poder computacional que los GCFG en su conjunto.
Por otro lado, las LCFRS son estrictamente más expresivas que las gramáticas indexadas linealmente y sus gramáticas adyacentes de árbol variante débilmente equivalentes (TAG). [2] La gramática principal es otro ejemplo de una LCFRS que es estrictamente menos poderosa que la clase de LCFRS en su conjunto.
LCFRS son débilmente equivalente a (set-local) multicomponentes TAGs ( MCTAGs ) y también con múltiples gramática libre de contexto (MCFGs [1] ). [3] y gramáticas minimalistas (MG). Los lenguajes generados por LCFRS (y sus equivalentes débiles) se pueden analizar en tiempo polinomial . [4]
Ver también
Referencias
- ↑ a b Weir, David Jeremy (septiembre de 1988). Caracterización de formalismos gramaticales levemente sensibles al contexto (PDF) (Ph.D.). Papel. AAI8908403. Universidad de Pennsylvania Ann Arbor.
- ^ Laura Kallmeyer (2010). Análisis más allá de las gramáticas libres de contexto . Springer Science & Business Media. pag. 33. ISBN 978-3-642-14846-0.
- ^ Laura Kallmeyer (2010). Análisis más allá de las gramáticas libres de contexto . Springer Science & Business Media. pag. 35-36. ISBN 978-3-642-14846-0.
- ^ Johan FAK van Benthem; Alice ter Meulen (2010). Manual de Lógica y Lenguaje (2ª ed.). Elsevier. pag. 404. ISBN 978-0-444-53727-0.