Benutzer:Sascha Brawer/Chomsky-Hierarchie
Die Chomsky-Hierarchie teilt formale Sprachen und Grammatiken in Klassen ein. Sie wurde ursprünglich 1956 von Noam Chomsky formuliert, der untersuchte, auf welche Weise der Aufbau menschlicher Sprachen wie des Englischen beschrieben werden kann.[1] Über ihre Bedeutung für die Linguistik hinaus ist die Chomsky-Hierarchie zu einem wichtigen Bestandteil der theoretischen Informatik geworden.[2] Aufgrund der Beiträge des Mathematikers Marcel Schützenberger zur Theorie formaler Sprachen wird die Chomsky-Hierarchie gelegentlich auch Chomsky-Schützenberger-Hierarchie genannt.
(Bild)
Natürliche Sprachen
Die Einordnung der natürlichen Sprachen in die Chomsky-Hierarchie war lange Zeit ungeklärt.
Chomsky zeigte in seiner ursprünglichen Arbeit von 1956, dass das Englische nicht regulär sein könne.[1]:115 Die Gültigkeit seiner Argumentation wurde später zwar in Frage gestellt, konnte jedoch auf andere Weise bewiesen werden.[3]
Hingegen war lange Zeit unklar, ob natürliche Sprachen kontextfrei sind. Chomsky vermutete lediglich, dass sich kontextfreie Grammatiken nicht als linguistische Theorie eignen würden, um den Aufbau natürlicher Sprachen elegant zu beschreiben. Im formalen Sinn musste er die Frage letztendlich offen lassen: „I do not know whether English is actually a [context-free] language or whether there are other actual languages that are literally beyond the bounds of phrase structure description.“[1]:119 Die Frage der Kontextfreiheit natürlicher Sprachen blieb daraufhin, trotz zahlreicher Versuche verschiedener Autoren, rund ein Vierteljahrhundert lang offen.[4] Erst 1985 konnte für das Schweizerdeutsche[5] und die westafrikanische Sprache Bambara[6] die Nicht-Kontextfreiheit gezeigt werden. In beiden Fällen beruht der Beweis auf einem Schnitt mit einer regulären Sprache, gefolgt von einer Anwendung des Schleifensatzes.
- Kontextsensitiv?
- Die von Chomsky formulierte Transformationsgrammatik ist äquivalent zu Turingmaschinen und damit in der Lage, beliebige rekursiv aufzählbarbare Sprachen zu erzeugen.[Bach and Marsh, 1978, zit. n. Savicth, Context-Sensitive Grammar and Natural Language Syntax]. Savitch argumentiert: TODO.
Sprachen
(Das folgende besser wegwerfen).
Die von der Chomsky-Hierarchie eingeteilten Sprachen sind mathematische Mengen von Wörtern über einem Alphabet. Zum Beispiel können mit dem Alphabet, das aus den beiden Zeichen a und b besteht, unter anderem folgende Sprachen gebildet werden:
- Sprache der Wörter mit 2 Zeichen
- Die Sprache { aa, ab, ba, bb }. Sie umfasst genau jene aus a und b gebildeten Wörter, die zwei Zeichen lang sind.
- Sprache a+
- Die Sprache { a, aa, aaa, aaaa, aaaaa, aaaaaa, ... }. Sie umfasst genau jene Wörter, die aus mindestens einem Vorkommen von a (und nichts anderem) bestehen.
- Sprache anbn
- Die Sprache { ab, aabb, aaabbb, aaaabbbb, ... }. Sie umfasst genau jene Wörter, die aus n Vorkommen von a bestehen (mit n > 0), gefolgt von gleich vielen Vorkommen von b.
Auf formale Sprachen sind die in der Mengenlehre üblichen Operationen anwendbar. Bildet man zum Beispiel die Schnittmenge aus a+ und der „Sprache der Wörter mit 2 Zeichen“, ist das Ergebnis die Sprache { aa }. — TODO:Bild.
Bedeutung in der Linguistik
(Wahrscheinlich besser weglassen, hmm)
Noam Chomsky führte formale Sprachen und Grammatiken als Werkzeug ein, um in der Linguistik präzise über den Aufbau menschlicher Sprachen, insbesondere des Englischen, sprechen zu können.[1] Entsprechend sah er die Grammatik als Theorie, welche die Struktur einer Sprache beschreibt. Insbesondere solle eine Grammatik in der Lage sein, korrekt vorherzusagen, ob eine Wortfolge vom Menschen als korrekt oder falsch aufgebaut empfunden wird. Zum Beispiel sind „John ate a sandwich“ und „Sandwich ate a John“ beides Abfolgen von englischen Wörtern. Ein des Englischen mächtiger Mensch wird aber nur den ersten Satz als korrektes Englisch einstufen. Eine Grammatik des Englischen sollte dies vorhersagen können.[1]:113
TODO: Wahrscheinlichkeit des Vorkommens; colorless green ideas[1]:116 — Vielleicht auch nicht nötig; es könnte auch vom eigentlichen Thema des Artikels ablenken.
Einzelnachweise
- ↑ a b c d e f Noam Chomsky: Three Models for the Description of Language. In: IRE Transactions on Information Theory. Nr. 2, 1956, S. 113–124, doi:10.1109/TIT.1956.1056813 (PDF-Datei; 1.5 MB).
- ↑ Association for Computing Machinery, IEEE Computer Society: Computer Science Curriculum 2008. Dezember 2008. (PDF-Datei; 562 kB).
- ↑ Gazdar/Pullum, Computationally Relevant Proverties of Natural Languages and their grammars. TODO: Originalarbeiten lesen und zitieren!
- ↑ Gazdar/Pullum, Natural Languages and CF Languages
- ↑ Stuart M. Shieber: Evidence Against the Context-Freeness of Natural Language. In: Linguistics and Philosophy, Band 8, 1985. Springer (Kluwer, Reidel), ISSN 0165-0157, S. 333–343 (PDF-Datei; 6.3 MB).
- ↑ Christopher Culy: The Complexity of the Vocabulary of Bambara. In: Linguistics and Philosophy, Band 8. Springer (Kluwer, Reidel), 1985, ISSN 0165-0157, S. 345–351 (PDF-Datei; 297 kB).
