Gramática generalizada libre de contexto

Concepto de teoría del lenguaje abstracto

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

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 , donde es una única tupla de cadenas o algún uso de una función de composición (potencialmente diferente) que se reduce a una tupla de cadenas. Las reglas de reescritura son 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\to f(Y,Z,...)}$ ${\displaystyle Y}$ ${\displaystyle Z}$

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

Ejemplo

Una traducción simple de una gramática libre de contexto a una GCFG se puede realizar 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}$

La producción de CF de abbbba es

S

comoSa

abSba

abbSbba

abbba

y la producción 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 }$

Sistemas de reescritura lineal libre de contexto (LCFRS)

Weir (1988) ^[1] describe dos propiedades de las funciones de composición, linealidad y regularidad. Una función definida como es lineal si y solo si cada variable aparece como máximo una vez en cada lado de = , lo que la 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 la hace regular pero no o . ${\displaystyle f(x_{1},...,x_{n})=...}$ ${\displaystyle f(x)=g(x,y)}$ ${\displaystyle f(x)=g(x,x)}$ ${\displaystyle f(x_{1},...,x_{n})=...}$ ${\displaystyle f(x,y)=g(y,x)}$ ${\displaystyle f(x)=g(x,y)}$ ${\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 lineal libre de contexto (LCFRS, por sus siglas en inglés). El 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 a árboles de variantes 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.

Los LCFRS son débilmente equivalentes a los TAG multicomponentes (MCTAG) (locales al conjunto) y también a las gramáticas libres de contexto múltiple (MCFG [1]). ^[3] y a las gramáticas minimalistas (MG). Los lenguajes generados por LCFRS (y sus equivalentes débiles) pueden analizarse en tiempo polinomial . ^[4]

Véase también

• Gramática de concatenación de rangos

Referencias

1. Weir, David Jeremy (septiembre de 1988). Caracterización de formalismos gramaticales ligeramente sensibles al contexto (PDF) (Ph.D.). Artículo. Vol. AAI8908403. Universidad de Pensilvania, Ann Arbor.
2. Laura Kallmeyer (2010). Análisis más allá de las gramáticas independientes del contexto. Springer Science & Business Media. pág. 33. ISBN 978-3-642-14846-0.
3. Laura Kallmeyer (2010). Análisis más allá de las gramáticas independientes del contexto. Springer Science & Business Media. pág. 35-36. ISBN 978-3-642-14846-0.
4. 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.