Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Samstag, 9. Mai 2015

Aufgepasst und mitgemacht!


Deutsch

Da ich in der Uni letz­tens das Pum­ping-Lem­ma für re­guläre Spra­chen ken­nen­ge­lernt ha­be, möchte ich heu­te mal ver­su­chen, zu zei­gen, dass die natürli­chen Spra­chen schwach kon­text­sen­si­tiv sind. Außer­dem möchte ich ver­su­chen, das Gan­ze so zu for­mu­lie­ren, dass es auch je­mand oh­ne in­for­ma­ti­sche Vor­bil­dung ver­steht. Über Re­so­nanz würde ich mich al­so sehr freu­en.

Zunächst ein­mal ei­ne kur­ze Einführung: Es gibt vier Ty­pen von for­ma­len Spra­chen (Typ 0–3). Al­le Spra­chen sind vom Typ 0. Die Typ-1-Spra­chen lie­gen in den Typ-0-Spra­chen, die Typ-2-Spra­chen in den Typ-1-Spra­chen und die Typ-3-Spra­chen in den Typ-2-Spra­chen. Ei­ne Typ-2-Spra­che ist al­so von den Ty­pen 0–2. Am ein­fachs­ten ist das nach­zu­voll­zie­hen, wenn man sich ein Men­gen­dia­gramm malt. Die Spra­chen von Typ 0 bis Typ 3 nennt man auch: re­kur­siv aufzähl­bar, kon­text­sen­si­tiv, kon­text­frei und re­gulär. Je höher der Typ ei­ner Spra­che ist, de­sto mehr Ein­schränkun­gen un­ter­liegt sie. Wir möchten zei­gen, dass natürli­che, d. h. vom Men­schen ge­spro­che­ne, Spra­chen schwach kon­text­sen­si­tiv sind, al­so zwi­schen Typ 1 und Typ 2 lie­gen. Das be­deu­tet, dass es natürli­che Spra­chen vom Typ 2 und natürli­che Spra­chen vom Typ 1 gibt.
Um zu zei­gen, dass ei­ne Spra­che von ei­nem be­stimm­ten Typ ist, muss man zei­gen, dass sie nicht von den Ty­pen höher­er Zahl ist. Al­so, müssen wir zei­gen, dass natürli­che Spra­chen nicht vom Typ 3 sind und dass es min­des­tens ei­ne gibt, die auch nicht vom Typ 2 ist. Das kann man mit dem so­ge­nann­ten Pum­ping-Lem­ma be­werk­stel­li­gen.
Das Pum­ping-Lem­ma für re­guläre Spra­chen (Typ 3) be­sagt Fol­gen­des: Al­le Wörter ei­ner re­gulären Spra­che mit ei­ner vor­ge­ge­be­nen Länge von n oder größer las­sen sich in die Be­stand­tei­le uvw zer­le­gen, so dass gilt: die Länge von v ist min­des­tens 1, die Länge von uv ist höchs­tens n und al­le Wörter uviw für ein be­lie­bi­ges i sind eben­falls in der Spra­che ent­hal­ten (vi be­deu­tet i-mal v hin­ter­ein­an­der).
Als nächs­tes wol­len wir mit dem Pum­ping-Lem­ma zei­gen, dass die natürli­chen Spra­chen (ge­nau­er: Deutsch) nicht re­gulär sind. Da­zu reicht es zu zei­gen, dass ein Teil des Deut­schen nicht re­gulär ist. Die­ser Teil sei­en Mit­te­lein­bet­tun­gen, al­so z. B.: Der Mann lach­te.Der Mann [der die Kuh sah] lach­te.Der Mann [der die Kuh [die den Hund trat] sah] lach­te.Der Mann [der die Kuh [die den Hund [...] trat] sah] lach­te. Sol­che Ein­bet­tun­gen sind theo­re­tisch un­end­lich oft hin­ter­ein­an­der möglich. Wir wol­len nun zei­gen, dass Sätze mit sol­chen Ein­bet­tun­gen nicht re­gulär sind. Aber zu­erst ein­mal müssen wir uns klar­ma­chen, was ein Wort in un­se­rem Fal­le über­haupt ist.
All­ge­mein be­steht ei­ne Spra­che aus Wörtern und ein Wort aus Al­pha­bet­sym­bo­len. In un­se­rem Fal­le sind die Wörter die Sätze und die Al­pha­bet­sym­bo­le die No­mi­nal- und Ver­bal­phra­sen. Dass be­deu­tet, dass wir ein Al­pha­bet mit nur zwei Sym­bo­len ha­ben: No­mi­nal­phra­sen (der Mann, die Kuh) und Ver­bal­phra­sen (lach­te, sah). (An die­ser Stel­le ha­be ich et­was ge­trickst und kei­ne Un­ter­schei­dung zwi­schen so­ge­nann­ten Ter­mi­nal- und Nicht­ter­mi­nal­sym­bo­len ge­macht, um die Sa­che nicht unnötig zu ver­kom­pli­zie­ren. Natürlich han­delt es sich bei der Mann und die Kuh um ver­schie­de­ne (Ter­mi­nal-)Sym­bo­le, aber für uns reicht es, im wei­te­ren Ver­lauf al­le No­mi­nal­phra­sen mit dem (Nicht­ter­mi­nal-)Sym­bol a und al­le Ver­bal­phra­sen mit b zu be­zeich­nen.) Of­fen­sicht­lich ha­ben wir al­so ei­ne Spra­che, die nur Wörter der Form akbk enthält, al­so Sätze mit ei­ner be­lie­bi­gen An­zahl (k) von No­mi­nal­phra­sen ge­folgt von der­sel­ben An­zahl Ver­bal­phra­sen.
Sei nun ei­ne Wortlänge n ge­ge­ben. Wir wählen aus un­se­rer Spra­che das Wort anbn aus, wel­ches so­mit die Länge 2·n hat und die Be­din­gung für das Pum­ping-Lem­ma (die Wortlänge muss min­des­tens n sein) erfüllt. anbn soll­te sich nun in uvw zer­le­gen las­sen, so dass die oben ge­nann­ten Be­din­gun­gen erfüllt sind. Da v min­des­tens 1 sein muss, ist uw ein Wort, das ohne Berück­sich­tung dum­mer Aus­nah­men so aus­sieht: ambn (oder anbm, aber da­zu geht der Be­weis ana­log), wo­bei m klei­ner als n ist. (Wir ha­ben das Wort anbn al­so ein­fach in die drei Tei­le u, v und w mit den Wer­ten am, an-m und bn zer­legt und las­sen nun das v in der Mit­te weg. Manch ei­ner mag an­mer­ken, dass v nicht nur aus glei­chen Al­pha­bet­sym­bo­len zu be­ste­hen braucht. Das ist kor­rekt, aber wenn v aus as und bs bestünde, wäre klar, dass uviw für je­des i>1 auf kei­nen Fall in der Spra­che ist, da in un­se­rem Wort dann as und bs durch­ein­an­der vorkämen.) Wir se­hen, dass ambn nicht in un­se­rer Spra­che liegt, da zu un­se­rer Spra­che nur Wörter mit der­sel­ben An­zahl as und bs gehören, un­ser Wort aber ei­ne un­ter­schied­li­che An­zahl auf­weist. Wäre die Spra­che re­gulär, so müss­ten al­le Wörter der Form uviw, al­so auch uv0w, zu ihr gehören. Da dies aber, wie wir se­hen, nicht der Fall ist, ist die Spra­che (und da­mit die deut­sche Spra­che) auch nicht re­gulär.
(An­mer­kung: In der Lin­guis­tik ist es um­strit­ten, ob wirk­lich al­le natürli­chen Spra­chen über sol­che oder ver­gleich­ba­re Ein­bet­tun­gen verfügen. Man­che Lin­guis­ten ver­tre­ten die Mei­nung, dass es re­guläre natürli­che Spra­chen gibt. Bis die­se Fra­ge aber endgültig ge­klärt ist, ge­hen wir mal da­von aus, dass al­le natürli­chen Spra­chen über Ein­bet­tun­gen verfügen, auch, wenn man sie bei ei­ni­gen noch nicht ent­deckt ha­ben soll­te.)
Als nächs­tes wol­len wir zei­gen, dass es Spra­chen gibt, die auch nicht kon­text­frei, son­dern kon­text­sen­si­tiv sind. Da­zu wird meis­tens Schwei­zer­deutsch her­ge­nom­men, wel­ches der­ar­ti­ge Kon­struk­tio­nen er­laubt: [de Karl] (d’Ma­ria) {em Pe­ter} |de Hans| [laat] (hälfe) {lärne} |schwüme| (über­kreuz­te Abhängig­keit). Im Hoch­deut­schen lau­te­te der­sel­be Satz: dass [der Karl] (die Ma­ria) {den Pe­ter} |den Hans| |schwim­men| {leh­ren} (hel­fen) [lässt] (wie­der mit Mit­te­lein­bet­tun­gen). Wir er­hal­ten dem­nach für das Schwei­zer­deut­sche Bei­spiel ei­ne Struk­tur von akblckdl. (Eben we­gen der über­kreuz­ten Struk­tur können wir nicht ein­fach anbn schrei­ben.)
Das Pum­ping-Lem­ma für kon­text­freie Spra­chen (Typ 2) sieht so ähn­lich aus wie das für re­guläre Spra­chen: Al­le Wörter ei­ner kon­text­frei­en Spra­che mit ei­ner vor­ge­ge­be­nen Länge von n oder größer las­sen sich in die Be­stand­tei­le uv­wxy zer­le­gen, so dass gilt: die Länge von vx ist min­des­tens 1 (d. h. v und x dürfen nicht bei­de leer sein), die Länge von vwx ist höchs­tens n und al­le Wörter uviwxiy für ein be­lie­bi­ges i sind eben­falls in der Spra­che ent­hal­ten. (Wie man sieht, ist der Wort­laut fast iden­tisch, es gibt nur ein paar Va­ria­blen mehr.) Der Be­weis mit dem Pum­ping-Lem­ma, dass das Schwei­zer­deut­sche nicht kon­text­frei ist, geht ähn­lich.
Es sei die Wortlänge n ge­ge­ben. Wir wählen aus un­se­rer Spra­che das Wort anbncndn aus, wel­ches so­mit die Länge 4·n hat und die Be­din­gung für das Pum­ping-Lem­ma erfüllt. anbncndn soll­te sich nun in uv­wxy zer­le­gen las­sen, so dass die oben ge­nann­ten Be­din­gun­gen erfüllt sind. Da vwx höchs­tens die Länge n ha­ben darf, können v und x nicht wei­ter als n-1 Schrit­te von­ein­an­der ent­fernt sein. Das be­deu­tet für uns, dass es vier mögli­che Fälle gibt: v und x be­ste­hen aus den­sel­ben Al­pha­bet­sym­bo­len, v be­steht aus as und x be­steht aus bs, v be­steht aus bs und x be­steht aus cs oder v be­steht aus cs und x be­steht aus ds. (Wie schon im ers­ten Be­weis können v und x je­weils nur aus ei­ner Art Al­pha­bet­sym­bol be­ste­hen, da sonst uviwxiy für je­des i>1 auf kei­nen Fall in der Spra­che wäre.)
Der ers­te Fall un­ter­teilt sich wie­der­um in vier Fälle (weil v und x aus as, bs, cs oder ds be­ste­hen können.) Es reicht aber, sich nur einen von ih­nen an­zu­schau­en, da die an­de­ren drei Fälle ana­log funk­tio­nie­ren: Sei­en v und x aus bs, dann zer­le­gen wir folg­lich das Wort anbncndn in die fünf Tei­le u, v, w, x und y mit den Wer­ten an, bt, bn-t-s, bs und cndn. Soll das Pum­ping-Lem­ma nun erfüllt sein, muss je­des Wort der Form uv iwxiy zu un­se­rer Spra­che gehören. Pro­bie­ren wir es al­ler­dings mit i=0, dann er­hal­ten wir uwy bzw. anbn-t-scndn, wel­ches nicht in un­se­rer Spra­che liegt, da wir ei­ne un­ter­schied­li­che An­zahl von bs und ds ha­ben (zur Er­in­ne­rung: t und s müssen in der Sum­me min­des­tens 1 er­ge­ben). So weit, so gut.
Es blei­ben noch die rest­li­chen drei Fälle (v und x be­ste­hen aus un­ter­schied­li­chen Al­pha­bet­sym­bo­len). Die­se drei Fälle funk­tio­nie­ren al­ler­dings wie­der ana­log zu­ein­an­der, al­so reicht es, nur einen Fall zu zei­gen: v be­steht aus bs und x be­steht aus cs. D. h. wir zer­le­gen das Wort anbncndn aber­mals in fünf Tei­le u, v, w, x und y mit den Wer­ten anbn-s-m, bs, bm, ct und cn-tdn. Las­sen wir nun wie­der die Tei­le v und x weg, er­hal­ten wir das Wort anbn-scn-tdn, wel­ches nicht in un­se­rer Spra­che liegt. So­mit ist Schwei­zer­deutsch nicht kon­text­frei.
Und so­mit sind natürli­che Spra­chen schwach kon­text­sen­si­tiv. Q. e. d.
Wer sich vor­hin ein Men­gen­dia­gramm ge­malt hat, kann die natürli­chen Spra­chen jetzt noch da­zu­zeich­nen.

1 Kommentar:

  1. Da du ja förmlich um einen Kommentar bettelst hab ich mich mal erbarmen lassen.
    Tatsächlich habe ich alles verstanden, auch wenn ich mich wie in der Schule fühlte, weil ich neben dem Lesen mit Zettel und Stift Stichpunkte gemacht habe.
    Ich denke, dass dieser Text ziemlich gut geschrieben ist, erklärt sich von selbst, da ihn sogar Leute die nicht im Geringsten etwas mit der Thematik zu tun haben mit Leichtigkeit nachvollziehen können (auch ohne jemals auf einer Spezialschule gewesen sein zu müssen :P ).

    AntwortenLöschen