{"id":2176,"date":"2009-01-11T18:26:38","date_gmt":"2009-01-11T17:26:38","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=2176"},"modified":"2023-05-25T07:31:48","modified_gmt":"2023-05-25T05:31:48","slug":"formale-sprachen-teil-1-die-chomsky-hierarchie","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2009\/01\/formale-sprachen-teil-1-die-chomsky-hierarchie.htm","title":{"rendered":"Formale Sprachen, Teil 1: Die Chomsky-Hierarchie"},"content":{"rendered":"
(25 Kommentare.<\/a>)<\/small> <\/div>\n

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

In der Informatik geht es um Information und deren automatische Verarbeitung. Ein Teilbereich hei\u00dft theoretische Informatik, und den mochte ich im Studium recht gerne. Jedenfalls viel lieber als technischere Informatik, Signal\u00fcbertragung und dergleichen.<\/p>\n\n\n\n

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 \u00fcber diese Sprachen aufzustellen und diese beweisen zu k\u00f6nnen. In diesem und einigen folgenden Blogeintr\u00e4gen will ich das ein wenig erkl\u00e4ren – auch deshalb, um mir selber die Details wieder in Erinnerung zu rufen.<\/p>\n\n\n\n

Grundbegriffe: Alphabet, Wort, Sprache, Grammatik<\/h3>\n\n\n\n

Alphabet:<\/strong>
Eine endliche Menge von Zeichen, zum Beispiel:<\/p>\n\n\n\n

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

    Wort:<\/strong>
    Diese Zeichen lassen sich beliebig aneinanderreihen, zum Beispiel so:<\/p>\n\n\n\n

      \n
    1. abccddzeffgg<\/li>\n\n\n\n
    2. abbbabba<\/li>\n\n\n\n
    3. derHundfrisstfrisstKatzedie<\/li>\n\n\n\n
    4. 999022332<\/li>\n<\/ol>\n\n\n\n

      Statt Aneinanderreihung sagt man einfach Wort<\/em>. Verwirrend ist vielleicht, dass das, was in einer nat\u00fcrlichen Sprache ein Satz ist, hier Wort<\/em> hei\u00dft.<\/p>\n\n\n\n

      Sprache:<\/strong>
      Jede Teilmenge aus der Menge aller m\u00f6glichen W\u00f6rter zu einem Alphabet. Zum Beispiel, angelehnt an die oben genannten Alphabete:<\/p>\n\n\n\n

        \n
      1. Die Menge aller W\u00f6rter (Aneinanderreihungen), die mit a beginnen.
        aaabc ist ein Wort der Sprache, baaac nicht<\/li>\n\n\n\n
      2. Die Menge aller W\u00f6rter, die genau sechs Zeichen lang sind.
        aaabbb ist ein Wort der Sprache, aaabb nicht<\/li>\n\n\n\n
      3. Die Menge aller W\u00f6rter, die einen sinnvollen deutschen Satz ergeben (wobei man noch genauer definieren muss, was sinnvoll<\/em> hei\u00dft).
        derHundmagdieKatze ist ein Wort der Sprache, derHundHundKatze nicht<\/li>\n\n\n\n
      4. Die Menge aller W\u00f6rter, die eine Primzahl darstellen.
        23 ist ein Wort der Sprache, 24 nicht<\/li>\n<\/ol>\n\n\n\n

        Grammatik:<\/strong>
        Wenn man eine Sprache, die aus endlich vielen W\u00f6rtern besteht, beschreiben m\u00f6chte, kann man nat\u00fcrlich einfach alle die W\u00f6rter in einer langen Liste aufz\u00e4hlen. Das ist aber un\u00fcbersichtlich. Und wenn die W\u00f6rter einer Sprache beliebig lang sein k\u00f6nnen (hei\u00dft in nat\u00fcrlicher Sprache: wenn die S\u00e4tze beliebig lang sein k\u00f6nnen), dann ist das sogar ganz unm\u00f6glich. Also gibt es endliche Grammatiken, die mit Hilfe von Ableitungsregeln die Sprache so beschreiben, dass mit Hilfe dieser Grammatik alle W\u00f6rter der Sprache erzeugt werden k\u00f6nnen.<\/p>\n\n\n\n

        Ein ganz simples Beispiel, angelehnt an nat\u00fcrliche Sprache:<\/p>\n\n\n\n

        Satz => Subjekt + Pr\u00e4dikat + Erg\u00e4nzung
        Subjekt => \"Sie\" oder \"Er\"
        Pr\u00e4dikat => \"lacht\" oder \"springt\"
        Pr\u00e4dikat => Pr\u00e4dikat + \"und\" + Pr\u00e4dikat
        Erg\u00e4nzung => \"oft\" oder \"nie\"<\/code><\/pre>\n\n\n\n
        Man f\u00e4ngt bei Satz<\/em> 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\u00fchrungszeichen stehen. Mit diesen Regeln kann man dann die S\u00e4tze „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.<\/p>\n\n\n\n
        Diese Grammatiken hei\u00dfen auch Phrasenstrukturgrammatiken. Davon gibt es verschiedene Arten.<\/p>\n\n\n\n
        Die Chomsky-Hierarchie<\/h3>\n\n\n\n
        Sie ist nach Noam Chomsky (vor ein paar Wochen 90<\/span> 80 geworden) benannt. Bei Chomsky treffen sich Sprachwissenschaft und Informatik. Und es wird kompliziert. Deshalb gebe ich hier einen wohl erst einmal unverst\u00e4ndlichen \u00dcberblick und werde in folgenden Blogebeitr\u00e4gen auf die einzelnen Sprachen der Hierarchie nach und nach eingehen.<\/p>\n\n\n\n