Formale Sprachen, Teil 1: Die Chomsky-Hierarchie

Mich hat noch nie jemand gefragt: Herr Rau, was lernt man eigentlich im Informatik-Studium? Deshalb hier eine Antwort.

In der Informatik geht es um Information und deren automatische Verarbeitung. Ein Teilbereich heißt theoretische Informatik, und den mochte ich im Studium recht gerne. Jedenfalls viel lieber als technischere Informatik, Signalübertragung und dergleichen.

In der theoretischen Informatik geht es unter anderem um Sprachen. Die sind dort allerdings als formale Sprachen sehr genau definiert. Denn das macht es leichter, Behauptungen über diese Sprachen aufzustellen und diese beweisen zu können. In diesem und einigen folgenden Blogeinträgen will ich das ein wenig erklären – auch deshalb, um mir selber die Details wieder in Erinnerung zu rufen.

Grundbegriffe: Alphabet, Wort, Sprache, Grammatik

Alphabet:
Eine endliche Menge von Zeichen, zum Beispiel:

  1. {a, b, c, d … z}
  2. oder auch nur {a, b}
  3. oder {Hund, Katze, Maus, der, die, das, frisst, jagt, mag}
  4. oder {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Wort:
Diese Zeichen lassen sich beliebig aneinanderreihen, zum Beispiel so:

  1. abccddzeffgg
  2. abbbabba
  3. derHundfrisstfrisstKatzedie
  4. 999022332

Statt Aneinanderreihung sagt man einfach Wort. Verwirrend ist vielleicht, dass das, was in einer natürlichen Sprache ein Satz ist, hier Wort heißt.

Sprache:
Jede Teilmenge aus der Menge aller möglichen Wörter zu einem Alphabet. Zum Beispiel, angelehnt an die oben genannten Alphabete:

  1. Die Menge aller Wörter (Aneinanderreihungen), die mit a beginnen.
    aaabc ist ein Wort der Sprache, baaac nicht
  2. Die Menge aller Wörter, die genau sechs Zeichen lang sind.
    aaabbb ist ein Wort der Sprache, aaabb nicht
  3. Die Menge aller Wörter, die einen sinnvollen deutschen Satz ergeben (wobei man noch genauer definieren muss, was sinnvoll heißt).
    derHundmagdieKatze ist ein Wort der Sprache, derHundHundKatze nicht
  4. Die Menge aller Wörter, die eine Primzahl darstellen.
    23 ist ein Wort der Sprache, 24 nicht

Grammatik:
Wenn man eine Sprache, die aus endlich vielen Wörtern besteht, beschreiben möchte, kann man natürlich einfach alle die Wörter in einer langen Liste aufzählen. Das ist aber unübersichtlich. Und wenn die Wörter einer Sprache beliebig lang sein können (heißt in natürlicher Sprache: wenn die Sätze beliebig lang sein können), dann ist das sogar ganz unmöglich. Also gibt es endliche Grammatiken, die mit Hilfe von Ableitungsregeln die Sprache so beschreiben, dass mit Hilfe dieser Grammatik alle Wörter der Sprache erzeugt werden können.

Ein ganz simples Beispiel, angelehnt an natürliche Sprache:

Satz => Subjekt + Prädikat + Ergänzung
Subjekt => „Sie“ oder „Er“
Prädikat => „lacht“ oder „springt“
Prädikat => Prädikat + „und“ + Prädikat
Ergänzung => „oft“ oder „nie“

Man fängt bei Satz an und ersetzt immer das links vom Pfeil durch das, was rechts vom Pfeil steht. Und das macht man immer so weiter, bis rechts nur noch Sachen in Anführungszeichen stehen. Mit diesen Regeln kann man dann die Sätze „Sie lacht oft“, „Sie lacht und springt nie“ oder „Er lacht und lacht und lacht oft“ erzeugen. Und unendlich viele mehr, wenn auch alle sehr langweilig sind.

Diese Grammatiken heißen auch Phrasenstrukturgrammatiken. Davon gibt es verschiedene Arten.

Die Chomsky-Hierarchie

Sie ist nach Noam Chomsky (vor ein paar Wochen 90 80 geworden) benannt. Bei Chomsky treffen sich Sprachwissenschaft und Informatik. Und es wird kompliziert. Deshalb gebe ich hier einen wohl erst einmal unverständlichen Überblick und werde in folgenden Blogebeiträgen auf die einzelnen Sprachen der Hierarchie nach und nach eingehen.

  • Chomsky 0: Alle Sprachen, die sich überhaupt durch eine Grammatik beschreiben lassen.
  • Chomsky 1: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextsensitive Grammatik beschreiben lassen.
  • Chomsky 2: Eine Teilmenge wiederum davon, nämlich die Sprachen, die sich durch eine kontextfreie Grammatik beschreiben lassen.
  • Chomsky 3: Eine Teilmenge wiederum davon, nämlich die Sprachen, die sich durch eine reguläre Grammatik beschreiben lassen.

Die Fragen, die sich stellen, sind: Was bedeuten all diese Wörter? Worin unterscheiden sich die verschiedenen Sprachen? Zu welcher Art gehören Programmiersprachen und menschliche Sprachen, wenn man das überhaupt sagen kann? (Und vielleicht noch: Gibt es Sprachen, die sich gar nicht durch eine Grammatik beschreiben lassen? Ja, gibt es.)

Zu jeder dieser Sprachen, zu jeder Grammatik kann man einen Automaten konstruieren, der – im besten Fall – für beliebige Wörter entscheidet, ob das Wort zu einer bestimmten Sprache gehört oder nicht. Für Chomsky 1-3 gibt es solche Automaten. Für Chomsky 0 ist es ein bisschen schwieriger.

Sprachen vom Typ Chomsky 0 heißen auch rekursiv aufzählbar oder semi-entscheidbar. Das heißt, alle dazu gehörenden Wörter können von einem Automaten (und zwar einer Turingmaschine) aufgezählt beziehungsweise bestätigt werden. Wenn ein Wort allerdings nicht zur Sprache gehört, dann sagt die Maschine nichts darüber. Man weiß also nicht, ob die Maschine noch rechnet oder für immer rechnen wird. Man kann zwar die (unendlich vielen) Wörter der Sprache aufzählen, aber nicht die (unendlich vielen) Wörter, die nicht dazu gehören. Anders gesagt, es gibt keine Grammatik für die Sprache derjenigen Wörter, die nicht zu einer gegeben 0-Sprache gehören.

Hier noch einmal im Überblick. In den nächsten Einträgen will ich jeden Sprachtyp etwas genauer erklären. Wenn man mit den einfachen Sprachen anfängt, geht das auch ganz harmlos.

Chomsky-Hierarchie Sprachtyp Grammatikart Akzeptierende Maschine
Chomsky 0 semi-entscheidbare/rekursiv aufzählbare Sprachen allgemeine Grammatik oder Phrasenstrukturgrammatik Turingmaschine
Chomsky 1 kontextsensitive Sprache kontextsensitive Grammatik (nichtdeterministische) linear beschränkte Turingmaschine
Chomsky 2 kontextfreie Sprache kontextfreie Grammatik Kellerautomat
Chomsky 3 reguläre Sprachen reguläre Grammatik (siehe auch reguläre Ausdrücke) endliche Automaten

Teil 2 folgt.

25 Antworten auf „Formale Sprachen, Teil 1: Die Chomsky-Hierarchie“

  1. Das ganze interessiert mich sehr, nicht nur wegen meiner FA (Codierungstheorie).
    Ich kann sie ja mal fragen: Herr Rau, was lernt man eigentlich im Informatik-Studium?

  2. Das lernt man nicht nur im Studium. In NRW ist das Teil des Zentral-Abitur-Stoffs, nicht unbedingt nur im LK. :-)

  3. Ich freue mich schon auf den restlich Teil dieser „Serie“. Ich frage mich schon länger, was man im Informatikstudium lernt. Programmiersprache(n)? Oder wie ein Computer arbeitet? Ich hoffe, dass werde ich in der nächsten Zeit dank ihres Blogs erfahren…

    Und obwohl michi es schon fragte:
    Was lernt man eigentlich im Informatikstudium?

  4. also eines kann ich schonmal beantworten zumindest in einem Hochschulstudium lernt man nicht programmieren – zumindest nicht der art das man sprache X lernt und noch weniger mit einem computer umgehen. Man lernt konzepte wie zB programmiersprachen funktionieren und aufgebaut sind, unter anderm braucht man obige grammatiken um compiler zu entwerfen. Das ganze studium beschaeftigt sich mit angewanter mathematik, die schoene namen wie logik, theoretische informatik und grundlagen der programmierung bekommen…

    S

  5. Kannitverstan.

    >Sprachen vom Typ Chomsky 0 heißen auch rekursiv aufzählbar oder semi-entscheidbar.

    Hier stock‘ ich schon. Was bitte ist „semi-entscheidbar“? Ich habe mir die Erklärung bei Wikipedia durchgelesen und ich habe nun eine vage Vorstellung davon. Dennoch halte ich den Begriff „semi-entscheidbar“ für sprachlichen Quatsch. Wenn man sich schon in einem Gebiet bewegt, in dem man alle Sinne beisammen haben muss, um nicht abzuhängen, dann sollte man die Sache nicht noch verkomplizieren, indem man Begriffe wählt, die schief oder gar paradox sind. Dafür kannst du natürlich nichts, du hast den Begriff ja nicht geprägt.

    >Das heißt, alle dazu gehörenden Wörter können von einem Automaten (und zwar einer
    >Turingmaschine) aufgezählt beziehungsweise bestätigt werden. Wenn ein Wort allerdings
    >nicht zur Sprache gehört, dann sagt die Maschine nichts darüber. Man weiß also nicht, ob
    >die Maschine noch rechnet oder für immer rechnen wird.

    Halt! Was ist der Input für die Turingmaschine? Erzeugt sie sich ihren Input selbst? Ist es ein mathematisches Perpetuum mobile? Du scheinst mir zwei verschiedene Aufgabenstellungen zu erwähnen: „alle dazu gehörenden Wörter können … aufgezählt bzw. bestätigt werden“ – ähm, wie? Was bekommt die Maschine gefüttert?

    Wenn es zu kompliziert zu erklären ist, gib dir keine Mühe. Wenn es aber möglich scheint, wäre ich dankbar. Ich habe mehrere Jahre in PL/I programmiert (nebenbei während des Studiums) und Kurse in PASCAL und SNOBOL besucht; ich nehme von mir an, dass ich einigermaßen logisch denken kann.
    Die animierte Grafik beim Wikipedia-Artikel „Turingmaschine“ ist sehr hübsch. Noch lieber wäre es mir allerdings, wenn man dazu noch erklärt bekäme, welche Nutzanwendung sich dazu denken ließe. Oder geht es „nur“ um Spielerei? Nicht dass ich das gering achten würde – „der Mensch ist nur da ganz Mensch, wo er spielt“, wie Jubilar Schiller zu sagen pflegte.

  6. Mir begegnete Chomsky im Studium, allerdings dem der Psychologie. Ich fand’s spannend und toll. („Farblose grüne Ideen schlafen wütend.“)
    Bin ebenfalls auf die weiteren Serienteile gespannt, dachte in Allg. Psychologie 1 (wo wir eben Chomsky behandelt haben) ohnehin öfter, dass es toll wäre, einen „leibhaftigen“ Informatiker im Seminarraum zu haben und über künstliche neuronale Netze etc pp und disziplinenspezifische Anwendung zu diskutieren…

  7. Mir begegnete Chomsky auch im Studium. Und zwar in einer Einführungsveranstaltung(!!) Sprachwissenschaft (für Primaten). Kernbereich der Veranstaltung war die „Transformationsgrammatik“.

    Die Veranstaltung hat den Teilnehmern der Veranstaltung gründlich den Spaß an der Transformationsgrammatik und Chomsky verdorben. ;)

    Markus

  8. MaMo: Abiturstoff? Ehrlich? Bei uns gibt es ja erst ab nächstem Jahr eine reguläre Kollegstufen-Informatik, zumindest als Alternative, ich weiß noch gar nicht, was da drin ist. Die ersten Automaten tauchen tatsächlich schon in 10 auf.

    Chomsky kenne ich aus der Sprachwissenschaft auf, aber nicht von einer Einführungsveranstaltung. Möglicherweise war mein Erstkontakt sogar nur eine scheinlose Übung zum Thema Computerlinguistik. Hängen geblieben ist nicht viel außer einem vagen Interesse. Und dann in England noch einmal. Dass der auch in der Psychologie auftaucht, wusste ich nicht.

    Transformationsgrammatik: Schade. Ist nämlich eigentlich ganz schön zum Spielen. Aber nichts für Einsteiger.

    rip: Das war jetzt nur der erste Überblick. Die nächsten beiden Einträge sind schon fast fertig, aber den für die Turingmaschine habe ich kaum angefangen. Ich dachte mir, ich warte auf Fragen in den Kommentaren, bevor ich mich daran mache, vielleicht kann ich sie dann besser erklären. Die Zusammenhänge sind zwar nur schwer und nicht furchtbar schwer, aber ich habe schon bei den einfacheren Automaten gemerkt, dass man sich da leicht unpräzise ausdrücken kann. Ich will aber sehen, ob ich das kann.

    Vorab: Die Turingmaschine, und die anderen Automaten auch, füttert man mit einem Wort. Der Automat arbeitet das Wort nach und nach ab und bleibt entweder in einem Zustand stehen, der „akzeptierend“ heißt (dann gehört das Wort zu der Sprache, die mit dem Automaten assoziiert ist), oder „nicht akzeptierend“ (dann nicht). Bei Chomsky 0 kann es auch sein, dass der Automat gar nicht stehen bleibt.
    Aufzählen=bestätigen: Eigentlich bestätigt der Automat nur einzelne Wörter. Wenn ich den Automaten allerdings zuerst mit allen einbuchstabigen Wörtern füttere und die akzeptierten notiere, dann mit allen zweibuchstabigen und die akzeptieren notiere, dann kann man mit dem Automaten doch nach und nach alle Wörter der Sprache aufzählen.

    Nutzanwendung: Keine. Aber der Automat ist quasi der kleinste denkbare Computer und so einfach gebaut, dass man an ihm bestimmte Sachen mathematisch beweisen kann. Und diese Sachen gelten dann für größere Computer genauso.

    (Ich kann ja danach mal einen Überblick übe das Studium Informatik geben. Und Englisch. Oder Deutsch.)

  9. Aber hallo Abiturstuff, mir hat das sehr gut gefallen und es hat wahrscheinlich bei meiner Studienwahl (Computerlinguistik) eine erhebliche Rolle gespielt. Wenn also die Möglichkeit besteht, das mit Schülern im Unterricht zu machen, ich ermutige dazu! Endliche Automaten für gegebene Sprachen zu basteln kann eine sehr spaßige Tüftelei sein.

  10. rip,

    der begriff semi-entscheidbar ist nicht paradox gewaehlt! Bei Entscheidbarkeit geht es immer um die Frage ob eine Aufgabe einer bestimmten Form beantwortet werden kann. Es geht da bei immer um Aufgaben, die sich mit ja oder nein Beantworten lassen. Fuer entscheidbare aufgaben kann man eine allgemeine Methode angeben, die die Aufgabe loest, fuer unentscheidbare gibt es keinen solchen Algorithmus. Semi-entscheidbare Aufgaben haben eine sehr lustige Eigenschaft: Es gibt einen Alg. der irgendwann JA ausgibt wenn die Antwort JA lautet, falls die Antwort NEIN lautet dann verfaengt er sich in einer Endlosschleife.

    Man könnte jetzt sagen, nagut dann muss man eben testen ob der Algo anhaelt oder nicht. Nur leider kann man beweisen, dass das sog. Halteproblem unentscheidbar ist.

    Um gleich die uebliche irritation zu vermeiden nur weil ein Aufgabentyp un- oder semi-entscheidbar ist, heist es nicht, dass man einzelne Aufgaben des Types nicht sehr wohl loesen kann. Es gibt nur eben kein Kochrezept fuer alle Aufgaben des Typs.

  11. @sts: Danke für deine Erklärung! Ich verstehe die Sache nun etwas besser, finde den Begriff „semi-entscheidbar“ aber immer noch unsinnig.
    Nach meinem Verständnis der Sachlage müsste es eher „aleatorisch-entscheidbar“ oder „ungewiss-entscheidbar“ heißen. „semi-“ heißt nun mal „halb-„, und das lässt sich ja wohl nicht voraussagen bei „semi-entscheidbaren“ Aufgaben, dass fünfzig Prozent der Läufe so und fünfzig Prozent anders ausgehen.

  12. Ja, das ist Abiturstoff in NRW, siehe http://www.standardsicherung.schulministerium.nrw.de/abitur-gost/fach.php?fach=15 . Zuerst fand ich das ziemlich langweilig, aber im Endeffekt war das wirklich super. Insgesamt war der Informatik-Unterricht in der Oberstufe wirklich eine prima Sache und hat im Hinblick auf das Informatik-Studium, wirklich einiges vorgegriffen, was mir den Einstieg erheblich erleichtert hat. Also, wer die Möglichkeit hat dies im Unterricht zu behandeln – nur zu! Gibt’s ja auch gute Tools zu, wurden hier ja auch tw. schon genannt.
    Übrigens sehr gute Artikel, nur weiter so. Habe ich sehr gerne gelesen!

  13. Chomsky hat sich übrigens auch als engagierter Politikkritiker einen Namen gemacht. – Ich habe ihn auch über die Linguistik kennengelernt und dann gestaunt, auf welchen Gebieten er sonst tätig war. – Die Kommentare zeigen: eine sehr nützliche Artikelreihe.

  14. rip, mag sein das der Begriff was die Wortbedeutung betrifft etwas ungluecklich ist, aber wenn man am Schreibtisch sitzt und dem Kind einen Namen geben muss sitzt man oft dumm da und man macht sich wenig gedanken, da die meisten Begriffe nicht lange leben, sagt man sich nun was solls und schreibt halt was. Nur manchmal ist eben eine Idee gut und dann verwenden schon soviele den Begriff das es kein zurueck mehr gibt. Semi wird in der Wissenschaft oft nicht im sinne von halb sondern teilweise benutzt, semipermeabel, faellt mir da spontan ein, heisst ja auch nicht das durch die Membran die haelfte der Molekuele durch kommen, sondern eben nur von einer seite einige – ist also eine Frage der Sichtweise.

  15. ich bin zur Zeit wie gestört auf der Suche nach Primärquellen von Chomsky, in denen er die Konzepte der Chomsky Hierarchie erklärt.

    Bisher habe ich nur Sekundärquellen aus dem Gebiet der Informatik gefunden, die die Chomsky Hierarchie beleuchten.(enstprechend mathematisch) Das macht Sinn, weil ja die Informatiker im Grunde Chomskys Idee* aufgegriffen haben und sich der Klassifikation bedient haben. Ich hab kein Problem damit, die Sekundärquellen zu verstehen (nicht zuletzt wegen DIESEM Blog ! ;) ) jedoch hätt ich gern etwas „aus erster Hand“.

    *genau das will ich finden. Das einzige was mir bis dato untegekommen ist, ist diese PDF: http://www.chomsky.info/articles/195609–.pdf (Noam Chomsky: Three models for the description of language) – die ist aber eher schwer zu lesen und ich komme nicht dahinter was auf diesen 12 Seiten explizit mit der Chomsky Hierarchie zu tun hat. (Er schreibt ja leider nicht: „And this is the definition of the Chomsky Hierarchy: “ :P

    Vielleicht kann Herr Rau ja weiterhelfen.

  16. So einer Herausforderung Bitte kann ich nicht widerstehen. Und das war dann auch spannende Lektüre! Ich liebe es, Wissenschaft beim Entstehen zuschauen zu können. Tatsächlich ist der Text schwer, und ich habe auch nicht alles verstanden. Aber ja, da geht es um die Chomsky-Hierarchie.

    Zuerst, in 2., beschreibt er Grammatiken und Sprachen vom Typ Chomsky 3. Sie heißen da nicht „regulär“, sondern „finite-state language/grammar“. In den Beispielsätzen (12) (i) bis (iii) nennt er Sprachen, die mit diesen Grammatiken nicht erzeugt werden können: anbn, die Palindromsprache, die Verdoppelungssprache. Danach beweist er, dass Englisch mit einer solchen Grammatik nicht erzeugt werden kann.

    In 2.4 untersucht er kurz die Möglichkeit, mit einer statistischen Methode Sätze zu erzeugen, verwirft das aber gleich mit seinem berühmten Satz, den ich jetzt zum ersten Mal im Kontext gelesen habe: „Colorless green ideas sleep furiously.“ Dieser Satz ist grammatisch korrekt, statistisch haben die Wörter aber kaum etwas miteinander zu tun.

    In 3. kommt Chomsky auf die vertrauten Phrasenstrukturgrammatiken, Typ Chomsky 2. Die Sprachen dazu nennt er „terminal languages“. (Wenn noch Nichtterminale drin sind: „derivable languages“, wenn ich das richtig verstanden habe.) In 3.5 benennt er das Verhältnis der Sprachen: „every finite-state language is a terminal language, but not conversely“. Also: jede reguläre Sprache ist auch eine kontextfreie Sprache.

    Am Ende von 3.6 gibt Chomsky zu, dass er nicht weiß, ob Englisch eine „terminal language“ ist, dass es aber genug (mathematische) Sprachen gibt, die sicher keine sind – sein altes Beispiel (12) (iii) etwa, die Verdoppelungssprache.

    In 5. kommt er zu den Transformationsgrammatiken. Da habe ich dann nicht mhr gründlich weiter gelesen; ich denke nicht, dass das den kontextsensitiven Sprachen entspricht. Allerdings: „transformational rules […] take into account a certain amount of constituent structure (i.e., a certain history of derivation).“ Das klingt schon ein bisschen nach Kontext. Zur weiteren Hierarchisierung habe ich allerdings nichts darin gefunden.

    Vielleicht weiiß jemand anderer mehr. Ich müsste mich richtig vertiefen, um etwas zu Chomskys Text ab 5. sagen zu können, und das mache ich erst, wenn ich irgendwann mal mein Die Chomsky-Hierarchie für Dummies angehe.

  17. vielen dank für die schnelle und vedammt ausführliche Antwort!

    Wir sind der Sache also auf der Spur ! :)

    Ich habe mir im Zuge dieser Ermittlungen die Freiheit genommen einen Thread bei matroids zu eröffnen und auf diese Rescherche hier aufmerksam zu machen:

    http://matheplanet.com/default3.html?topic=123997=5100

    da wird mir empfohlen syntactic structurus anzuschauen

    http://books.google.com/books?id=a6a_b-CXYAkC&dq=syntactic+structures+chomsky&printsec=frontcover&source=bn&hl=de&ei=4o0tSr-OLI_BsAb43pTTCQ&sa=X&oi=book_result&ct=result&resnum=4.

  18. Auch die Klasse der kontextsensitiven Sprachen wird von den zugehörigen Automaten (LBAs) nur so erkannt, dass der Automat genau dann hält, wenn die Eingabe zur Sprache gehört. (Alle diese Sprachen sind natürlich nicht nur semi-entscheidbar, sondern sogar entscheidbar – aber eben nur von Turing-Maschinen.)

  19. Ich wollte das auch nicht anders verstanden haben. Vielen Dank für die Ergänzung, bin schon gespannt, ob noch mehr kommt.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.