Dependencias entre series

En lingüística , las dependencias seriales cruzadas (también llamadas dependencias cruzadas por algunos autores ^{[ 1 ]} ) ocurren cuando las líneas que representan las relaciones de dependencia entre dos series de palabras se cruzan entre sí. ^{[ 2 ]} Son de particular interés para los lingüistas que desean determinar la estructura sintáctica del lenguaje natural; las lenguas que contienen un número arbitrario de ellas no son libres de contexto . Por este motivo, se ha demostrado que el neerlandés ^{[ 3 ]} y el alemán suizo ^{[ 4 ] no son libres de contexto.}

Dejar${\displaystyle L_{SG}}$ser el conjunto de todas las oraciones en alemán suizo. Demostraremos matemáticamente que${\displaystyle L_{SG}}$no es independiente del contexto.

En las oraciones del alemán suizo, el número de verbos de un caso gramatical (dativo o acusativo) debe coincidir con el número de objetos de ese caso. Además, una oración que contenga un número arbitrario de tales objetos es admisible (en principio). Por lo tanto, podemos definir el siguiente lenguaje formal , un subconjunto de${\displaystyle L_{SG}}$:$${\displaystyle L={\text{De enero}}{\text{ s}}{\ddot {\mathrm {a} }}{\text{it}}{\text{ das}}{\text{ mer}}{\text{ (d'chind)}}{}^{m}{\text{ (em}}{\text{ Hans)}}{}^{n}{\text{ s}}{\text{ huus}}{\text{ h}}{\ddot {\mathrm {a} }}{\text{nd}}{\text{ wele}}{\text{ (laa)}}{}^{m}{\text{ (h}}{\ddot {\mathrm {a} }}{\text{lfe)}}{}^{n}{\text{ aastriiche.}}}$$Por lo tanto, tenemos${\displaystyle L=L_{SG}\cap L_{r}}$, dónde${\displaystyle L_{r}}$es el lenguaje regular definido por$${\displaystyle L={\text{De enero}}{\text{ s}}{\ddot {\mathrm {a} }}{\text{it}}{\text{ das}}{\text{ mer}}{\text{ (d'chind)}}{}^{+}{\text{ (em}}{\text{ Hans)}}{}^{+}{\text{ s}}{\text{ huus}}{\text{ h}}{\ddot {\mathrm {a} }}{\text{nd}}{\text{ wele}}{\text{ (laa)}}{}^{+}{\text{ (h}}{\ddot {\mathrm {a} }}{\text{lfe)}}{}^{+}{\text{ aastriiche.}}}$$donde el símbolo de más en superíndice significa "una o más copias". Dado que el conjunto de lenguajes libres de contexto es cerrado bajo la intersección con lenguajes regulares, solo necesitamos demostrar que${\displaystyle L}$no es independiente del contexto (, ^{[ 5 ]} pp 130–135).

Después de una sustitución de palabras,${\displaystyle L}$es de la forma${\displaystyle \{xa^{m}b^{n}yc^{m}d^{n}z|m,n\geq 1\}}$. Desde${\displaystyle L}$se puede asignar a${\displaystyle L'}$Según el siguiente mapa:${\displaystyle x,y,z\mapsto \epsilon ;a\mapsto a;b\mapsto b;c\mapsto c}$y dado que los lenguajes libres de contexto son cerrados bajo mapeos de símbolos terminales a cadenas terminales (es decir, un homomorfismo ) (, ^{[ 5 ]} pp 130–135 ), solo necesitamos demostrar que${\displaystyle L'}$no es independiente del contexto.

${\displaystyle L'=\{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}}$es un ejemplo estándar de lenguaje no libre de contexto (, ^{[ 5 ]} p.  128). Esto se puede demostrar mediante el lema de Ogden .

Supongamos que el lenguaje es generado por una gramática libre de contexto, entonces sea:${\displaystyle p}$Sea la longitud requerida en el lema de Ogden, entonces considere la palabra${\displaystyle a^{p}b^{p}c^{p}d^{p}}$en el idioma y marca las letras${\displaystyle b^{p}c^{p}}$Entonces, no se pueden satisfacer todas las tres condiciones que implica el lema de Ogden.

Se puede demostrar de manera similar que todas las lenguas habladas conocidas que contienen dependencias seriales cruzadas no son libres de contexto. ^{[ 2 ]} Esto llevó al abandono de la Gramática de Estructura de Frase Generalizada una vez que se identificaron dependencias seriales cruzadas en lenguas naturales en la década de 1980. ^{[ 6 ]}

Research in mildly context-sensitive language has attempted to identify a narrower and more computationally tractable subclass of context-sensitive languages that can capture context sensitivity as found in natural languages. For example, cross-serial dependencies can be expressed in linear context-free rewriting systems (LCFRS); one can write a LCFRS grammar for ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}$ for example.^[7][8][9]