Tvärserieberoenden

Ett schema som visar tvärseriella beroenden. Lägg märke till att w och v, som representerar ord, bildar respektive serie. Lägg också märke till att linjerna som representerar beroenderelationerna överlappar varandra.

Inom lingvistik uppstår tvärserieberoenden (även kallade korsningsberoenden av vissa författare) när linjerna som representerar beroenderelationerna mellan två serier av ord korsar varandra . De är av särskilt intresse för lingvister som vill bestämma det naturliga språkets syntaktiska struktur; språk som innehåller ett godtyckligt antal av dem är inte kontextfria . Genom detta faktum holländska och schweizisk-tyska visat sig vara icke-kontextfria.

Exempel

En schweizisk-tysk mening som innehåller tvärseriella beroenden (visas som linjer mellan verben och deras objekt). Den engelska översättningen med dess beroenden, som inte korsar varandra, visas för jämförelse.

Ett mer komplicerat exempel.

Eftersom schweizisk-tyska tillåter att verb och deras argument sorteras seriellt, har vi följande exempel, hämtat från Shieber:

... mer	em Hans	es	huus	hälfed	aastriiche.
... vi	Hans ( dat )	de	hus ( enl )	hjälp	måla.

Det vill säga "vi hjälper Hans att måla huset."

Lägg märke till att de sekventiella substantivfraserna em Hans ( Hans ) och es huus ( huset ), och de sekventiella verben hälfed ( hjälp ) och aastriiche ( måla ) båda bildar två separata serier av beståndsdelar. Lägg också märke till att dativverbet hälfed och ackusativverbet aastriiche tar dativen em Hans respektive ackusativ es huus som sina argument.

Icke-sammanhangsfrihet

Låt $L_{SG}$ vara mängden av alla schweizisk-tyska meningar. Vi kommer att bevisa matematiskt att $L_{SG}$ inte är kontextfri.

I schweizisk-tyska meningar måste antalet verb i ett grammatiskt kasus (dativ eller ackusativ) matcha antalet objekt i det kasus. Dessutom är en mening som innehåller ett godtyckligt antal sådana objekt tillåten (i princip). Därför kan vi definiera följande formella språk , en delmängd av $L_{SG}$ :

$$L={\text{De Jan}}{\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.}}$$

Således har vi $L=L_{SG}\cap L_{r}$ , där $L_{r}$ är det vanliga språket som definieras av

$$L={\text{De Jan}}{\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.}}$$

där den upphöjda plussymbolen betyder "en eller flera kopior". Eftersom uppsättningen av kontextfria språk är stängd under korsning med vanliga språk, behöver vi bara bevisa att $L$ inte är kontextfri (, s 130--135).

Efter en ordsubstitution har $L$ formen $\{xa^{m}b^{n}yc^{m}d^{n}z|m,n\geq 1\}$ . Eftersom $L$ kan mappas till $L'$ med följande karta: ${\displaystyle x,y,z\mapsto \epsilon ;a\mapsto a;b\mapsto b;c\mapsto c} , och eftersom$ de sammanhangsfria språken är stängda under mappningar från terminalsymboler till terminalsträngar ( det vill säga en homomorfism ) (, s 130--135), behöver vi bara bevisa att $L'$ inte är kontextfri.

${\displaystyle L'=\{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}} är ett standardexempel på$ icke -kontextfritt språk (, s. 128). Detta kan visas av Ogdens lemma .

Anta att språket genereras av en kontextfri grammatik, låt sedan $p$ vara den längd som krävs i Ogdens lemma, betrakta sedan ordet $a^{p}b^ {p}c^{p}d^{p}$ i språket och markera bokstäverna $b^{p}c^{p}$ . Då kan inte alla de tre villkoren i Ogdens lemma vara uppfyllda.

Alla kända talade språk som innehåller tvärseriella beroenden kan på liknande sätt bevisas inte vara kontextfria.

Behandling

Forskning inom milt kontextkänsligt språk har försökt identifiera en smalare och mer beräkningsmässigt hanteringsbar underklass av sammanhangskänsliga språk som kan fånga kontextkänslighet som finns i naturliga språk. Till exempel kan tvärseriella beroenden uttryckas i linjära kontextfria omskrivningssystem (LCFRS); man kan skriva en LCFRS-grammatik för { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1} till exempel.