Amazon reviews

Dieses Genre ist mir bisher entgangen: Surreale Amazon-Kritiken.

  • The Secret The Secret – ein Self-Help-Bestseller. Die Kritik beginnt harmlos: “Please allow me to share with you how ‘The Secret’ changed my life and in a very real and substantive way allowed me to overcome a severe crisis in my personal life.” Dann wird es aber schräg. Vom gleichen Autor gibt es noch mehr solcher Kritiken.
  • Bic Kugelschreiber.
  • Playmobil Security Checkout.
  • Der Besen “Harry Potter Nimbus 2000” ist aus dem Programm genommen, die allesamt positiven Kritiken sind gelöscht. Hier sind die Texte archiviert. Ich sag nur soviel: Besen. Zum drauf reiten. Batteriebetrieben. Mit Vibrationseffekt.

(Alles gefunden bei peterdavid.net.)

Formale Sprachen, Teil 3: Kontextfreie Sprachen

Das ist die Fortsetzung dieses Eintrags. Aber danach gibt es erst mal wieder Blogeinträge, die vielleicht von allgemeinerem Interesse sind, bevor ich mich dann an die richtig schwierigen Sachen wage.

Nehmen wir als Alphabet wieder nur {a, b}. Aus diesen zwei Zeichen kann man unendlich viele Wörter kombinieren. Greifen wir eine Teilmenge davon heraus, dann ist das eine Sprache. Die Sprache zum Beispiel, die aus allen Wörtern besteht, die genau so oft den einen wie den anderen Buchstaben enthalten, ist eine kontextfreie Sprache, vom Typ Chomsky 2. Sie kann durch eine kontextfreie Grammatik beschrieben werden; ihre Wörter werden von einem Kellerautomaten akzeptiert. (Mit der regulären Grammatik vom letzten Eintrag kann man diese Sprache nicht beschreiben.)

1. Kontextfreie Grammatik

1. S => aSB
2. S => bSA
3. S => ε (das heißt so viel wie nichts/null)
4. A => aS
5. B => bS

Diese Grammatik beschreibt die Sprache aller Wörter über {a, b}, in denen beide Buchstaben gleich oft vorkommen, einschließlich des leeren Worts.
Das Wort ababba kann man mit den Regeln so ableiten, fett gedruckt ist jeweils das Nichtterminal, das in der folgenden Zeile ersetzt wird:

Regel 1: S => aSB
Regel 5: => aSbS
Regel 2: => aSbbSA
Regel 3: => aSbbA
Regel 4: => aSbbaS
Regel 3: => aSbba
Regel 2: => abSAbba
Regel 4: => abSaSbba
Regel 3: => abSabba
Regel 3: => ababba

Und fertig. Gibt es eine kürzere Ableitung des Wortes? Gibt es eine kürzere Grammatik, die dieselbe Sprache beschreibt? Mir gefällt dieses ε nicht, da gehört das leere Wort ja auch zur Sprache; kann ich die Grammatik auch ohne das schreiben? Legitime Fragen, auf die es Antworten gibt.

Für eine kontextfreie Grammatik gelten folgende Einschränkungen:

  • Links vom Pfeil steht immer nur genau ein Nichtterminalzeichen. (Im Beispiel: Großbuchstaben.)
  • Rechts vom Pfeil dürfen Terminale und Nichtterminale in beliebiger Folge und Anzahl stehen. Außerdem darf es eventuell noch die Regel S => ε geben.

Gibt es überhaupt Sprachen, bei denen es wichtig ist, dass genau so oft das eine Zeichen auftaucht wie das andere? Aber ja. Stellen wir uns nur die Zeichen “(“ und ”)” oder “{“ ”}” oder “if” und “endif” vor – bei jedem Computerprogramm, bei jedem deutschen Satz, bei dem eine Klammer aufgemacht wird, muss auch wieder eine zugemacht werden. Wenn das brav nacheinander geschieht – Klammer auf, Klammer zu, Klammer auf, Klammer zu – dann geht das zur Not auch mit einer regulären Sprache. Aber sobald man verschachteln kann, sobald es Klammern in Klammern gibt, dann braucht man eine kontextfreie Grammatik. Und verschachteln kann man eben auch in natürlicher Sprache, wo eine Nominalphrase als Genitivattribut wieder eine Nominalphrase enthalten kann, die als Präpositionalattribut wieder eine Nominalphrase enthalten kann, und so weiter.

2. Kellerautomat

“Keller” ist die deutsche Übersetzung des englischen “stack”. Man kann auch Stapel dazu sagen. Ein Stapel kann beliebig hoch werden (ein Keller beliebig tief), man kann immer noch etwas drauflegen. Abgebaut wird der Stapel in umgekehrter Reihenfolge. Man kann also nicht unmittelbar auf ein Element mitten im Stapel zugreifen, sondern muss erst das abarbeiten, was darüber liegt.
Den Kellerautomaten will ich hier nicht beschreiben. Es sei nur gesagt, dass er eben über einen Keller/Stapel/stack verfügt, der beliebig groß werden kann. Das ist der Hauptunterschied zum endlichen Automaten. Es gibt auch beim Kellerautomaten einen Startzustand und mindestens einen akzeptierenden Zustand, wohl auch mehrere nicht akzeptierende Zustände. Wenn das Wort abgearbeitet ist, bleibt der Automat in einem Zustand stehen. Immer. Bleibt er in einem akzeptierenden Zustand stehen, gehört das Wort zur Sprache, sonst nicht.

(“Stack” kennt man auch vom “stack overflow”, einer typischen Sicherheitslücke beim Programmieren.)

3. Beispiele

1. Programmiersprachen

Alle Programmiersprachen können mit einer kontextfreien Grammatik beschrieben werden. Hier ist eine nicht ganz vollständige Grammatik in der übersichtlicheren Backus-Naur-Form, die die Programmiersprache von Robot Karol beschreibt. Die Grammatik lässt allerdings noch keine selbst definierten Anweisungen und Bedingungen zu, Absätze und Kommentare, die die Übersichtlichkeit erhöhen, habe ich ebenfalls weggelassen. Im Prinzip wären das aber jeweils nur wenige Zeilen mehr.

<Programm> :: = <Anweisung>
<Anweisung> ::= <vordefinierte Anweisung> |<Sequenz> | <Entscheidung> | <Wiederholung>
<vordefinierte Anweisung> ::= "linksDrehen" | "rechtsDrehen" | "Schritt" | "Hinlegen" | "Aufheben" | "MarkeSetzen" | "MarkeAufheben"
<Sequenz> :: = <Anweisung>*
<Entscheidung> ::= "wenn" <Bedingung> "dann" <Anweisung> "sonst" <Anweisung> "*wenn"
<Bedingung> ::= "istWand" | "nichtIstWand"| "istZiegel"| "nichtIstZiegel" |"istMarke" | "nichtIstMarke"
<Wiederholung> ::= <Wiederholung mit Bedingung> | <Wiederholung mit fester Anzahl>
<Wiederholung mit Bedingung> ::= "wiederhole solange" <Bedingung> <Anweisung> "*wiederhole"
<Wiederholung mit fester Anzahl> ::= "wiederhole" <Zahl> "mal" <Anweisung> "*wiederhole"
<Zahl> ::= <Zahl>+
<Zahl> ::= 1|2|3|4|5|6|7|8|9|0

Alles in spitzen Klammern ist ein Nichtterminal, <Programm> ist der Startpunkt, alles in Anführungszeichen ist ein Terminal. Wer sich an diese Grammatiken hält, erzeugt immer ein “Wort” der Robot-Karol-Sprache – will heißen, immer ein syntaktisch korrektes Robot-Karol-Programme. Ob das Programm auch das tut, was man möchte, ist eine andere Frage, ebenso die, ob das Programm zur Laufzeit einen Fehler ergibt, also ob Robot Karol gegen eine Wand läuft.

2. Eine Grammatik, angelehnt an die natürliche Sprache

<Satz> ::= <Nominalphrase> <Verbalphrase>
<Nominalphrase> ::= <Determiner> <Nomen>
<Determiner> ::= der | das | die | dieser | dieses | diese | jener | jenes | jene
<Nomen> ::= Hund | Katze | Maus | Mann | Frau | Kind | Knochen
<Verbalphrase> ::= <VerbTransitiv> <Nominalphrase>
<VerbTransitiv> ::= fraß | küsste | suchte | fand | warf

Damit kann man solche “Wörter” (wir nennen sie sonst: Sätze) ableiten:

                   Satz
                 /     \
               NP       VP   
              / \      /   \  
             D   N    V    NP
          Jene Katze fraß  / \
                          D   N
                         die Maus

Warum passt diese Art Grammatik eher zur englischen Sprache? Schon mal, weil “the” sich weder durch Numerus, Kasus noch Genus ändert, anders als im Deutschen. Damit man also Sätze verhindert wie: “Der Katze fraß den Maus”, muss man die Regeln noch weit verfeinern. Mehr dazu – aus der sprachwissenschaftlichen, nicht der informatischen Seite – bei: generative Grammatik (Wikipedia).

3. Logische Ausdrücke

<wff> ::= p | q | r |s
<wff> ::= N<wff>
<wff> ::= K<wff><wff> | A<wff><wff> | E<wff><wff> | C<wff><wff>

Mit diesen Regeln kann man Ausdrücke erzeugen wie {p, q, r, s, Np, Nq, Nr, Ns, Kpp, Kpq, NKpq, KpANpEqq … } – und diese Ausdrücke bedeuten etwas (ich sag nur WFF ‘N PROOF).

4. Das Wortproblem für kontextfreie Sprachen

Das Wortproblem wird später noch einmal wichtig. Es lautet: Kann man einen Algorithmus bauen (also zum Beispiel einen solchen Automaten), der für jedes beliebige Wort zu einem gegebenen Alphabet in endlicher Zeit entscheidet, ob das Wort zu einer bestimmten Sprache gehört oder ob es nicht dazu gehört? Ja, man kann. Für kontextfreie Sprachen ist das Wortproblem entscheidbar. Nach endlicher Zeit bleibt der Kellerautomat stehen, und zwar entweder in einem akzeptierenden Zustand oder nicht.

5. Zusammenfassung

Kontextfreie Sprachen sind wichtig für die Entwicklung und Umsetzung von Programmiersprachen. Auch natürliche Sprachen können – falls überhaupt – mit einer kontexfreien Grammatik beschrieben werden. (Nachtrag. Stimmt so nicht, siehe Kommentar unten.) Aber nicht alle Sprachen kann man mit einer kontextfreien Grammatik erzeugen. Das Standardbeispiele ist aibici, also die Sprache aller Wörter, die aus einer Reihe von a’s bestehen, gefolgt von ebenso vielen b’s, gefolgt von ebenso vielen c’s.

Teil 4 folgt nach einer kleinen Pause.

Formale Sprachen, Teil 2: Reguläre Sprachen

Das ist die Fortsetzung dieses Eintrags.

Heute will ich einen Einblick geben darüber, was eine Sprache vom Typ Chomsky 3 ausmacht. Diese Sprachen heißen reguläre Sprachen, sie können durch eine reguläre Grammatik (oder durch einen regulären Ausdruck) beschrieben werden. Mit einem endlichen Automaten kann man überprüfen, ob ein Wort zu einer Sprache gehört oder nicht.

Vorweg: Ich bin mir sicher, dass sich der eine oder andere Fehler eingeschlichen hat, und bin um Berichtigung dankbar. Vor allem reguläre Ausdrücken kenne ich nur aus der theoretischen Informatik, und mit der praktischen Anwendung in Perl-Syntax kenne ich mich nur wenig aus; über backreferences schreibe ich gar nichts. Ist ja auch kein RegEx-Tutorial.

1. Reguläre Ausdrücke

Am bekanntesten ist wohl der reguläre Ausdruck (regular expression, RegEx), auch wenn der Begriff vielleicht nicht jedem etwas sagt. Deshalb drei Beispiele.

1. Wenn ich in Spam Karma, einem verbreiteten Anti-Spam-Plugin für Wordpress, eine Spam-Quelle auf die Blacklist setzen möchte, dann geschieht das über einen regulären Ausdruck. Möchte ich zum Beispiel alle Kommentare als Spam markieren lassen, die das Wort “Sex” enthalten, dann gebe ich in Spam Karma im entsprechenden Feld ein: /Sex/. (Die Schrägstriche müssen sein, weil so in Perl-Syntax ein regulärer Ausdruck markiert wird.)
Nun kann es aber sein, dass findige Leute die Blockierung umgehen, indem sie stattdessen das Wort “Seeex” benutzen. Ich könnte natürlich nacheinander /Sex/, /Seex/, /Seeex/ und so weiter sperren, aber das wäre viel Arbeit. Stattdessen kann ich /Se+x/ schreiben. Das Pluszeichen gibt an, dass das Zeichen davor beliebig oft, aber mindestens einmal, erscheinen kann. /Se+x/ beschreibt also die Sprache, die aus den Wörter {Sex, Seex, Seeex, Seeeex, Seeeeex …} besteht.

2. Ein weiteres Beispiel betrifft Hotlinking. So heißt das,wenn zum Beispiel jemand ohne meine Erlaubnis eines der Bilder auf meiner Webseite bei sich in seiner Seite einbaut – und zwar nicht etwa eine bei sich gespeicherte Kopie des Bildes, sondern direkt meine verlinkt. (Gerne geschieht das bei Foren-Bildchen.) Das macht man aus verschiedenen Gründen nicht. Je nach Lust und Laune sperre ich diese Möglichkeit manchmal, oder sorge dafür, dass statt des eigentlich anvisierten Bildes und trotz dessen korrekter Adresse ein ganz anderes Bild bei der fremden Seite angezeigt wird. Möglich macht das eine Datei, die .htaccess heißt, die uns hier nicht weiter interessieren soll. In dieser Datei steht dann zum Beispiel, dass Browseranfragen von folgender Adresse ignoriert oder umgeleitet werden sollen:

(www\.)?frecherhotlinker\.(de|com)

Das Fragezeichen heißt, dass das Element davor – also das in den Klammern – ein oder keinmal auftauchen kann, der gerade Strich am Schluss heißt, dass entweder das Element links oder das rechts davon erscheinen kann. Der reguläre Ausdruck schließt also folgende Adressen ein: {www.frecherhotlinker.de, www.frecherhotlinker.com, frecherhotlinker.de, frecherhotlinker.com}. – Der Schrägstrich vor dem Punkt heißt nur, dass der Punkt tatsächlich als Punkt betrachtet werden soll. Sonst ist der Punkt nämlich die Abkürzung für “beliebiges Zeichen”, das man sonst umständlicher als (a|b|c|d|1|2|3|…) schreiben müsste.

3. Die Suchfunktion unter Open Office und anderen Textverarbeitungsprogrammen benutzt auch reguläre Ausdrücke. Ich kann suchen/ersetzen nach “grey” oder “gray”, indem ich den regulären Ausdruck “grey|gray” verwende. Ich kann suchen nach “favour” oder “favor”, indem ich entweder “favour|favor” verwende, oder “fav(o|ou)r”, oder “favou?r”. Das Fragezeichen heißt auch hier: erscheint 0 oder 1 mal.
(Open Office: Bei der Suchfunktion unter “Mehr Optionen” das Kästchen “regulärer Ausdruck” ankreuzen. Keine Schrägstriche am Anfang und Ende machen.)

Etwas komplizierter: Ich will in einem Text alle geklammerten Ausdrücke löschen. Dazu kann ich unter Open Office nach folgendem Ausdruck suchen: \(.*\) – dabei steht . für beliebiges Zeichen, * für eine beliebige Wiederholung solcher Zeichen, und (.*) heißt dann, dass links und rechts davon eine Klammer stehen soll. Die Schrägstriche müsssen dummerweise sein, weil die Klammern in RegEx-Syntax ja selber schon eine Sonderfunktion haben; die Schrägstriche teilen dem Programm mit, dass hier wirklich nur einfache echte Klammern gemeint sind. Aber aufgepasst: dieser Ausdruck umfasst innerhalb eines Absatzes auch Kombinationen wie: (aaa) bbb (aaa), wo man eigentlich die b’s in der Mitte nicht mit gemeint hat. Mehr zu Klammern beim nächsten Mal.

Auch sonst tauchen reguläre Ausdrücke an allen möglichen Ecken und Enden des Computers auf. Generell gilt: Mit einem RegEx kann man verschiedene Arten von Wörtern herausfiltern oder suchen.
Von einer anderen Perspektive aus betrachtet, heißt das: Alle Wörter, die zu dem RegEx passen, gehören zu einer Sprache. Ich will ein paar Beispiele geben. Weil es übersichtlicher und einfacher ist, beschränke ich mich auf das Alphabet {a, b, c}. Ich will mich auch auf einige wenige RegEx-Kürzel beschränken: | heißt “oder”, * heißt: beliebig oft (auch keinmal).

  • Die Sprache aller zweibuchstabigen Wörter, die mit einem a beginnen?
    Sprache: {aa, ab, ac}
    RegEx: a(a|b|c)
  • Die Sprache aller Wörter überhaupt, die mit einem a beginnen?
    Sprache: {a, aa, ab, ac, aaa, aab, aac, aba, abb, abc, aca, acb, acc, aaaa…}
    RegEx: a(a|b|c)*
  • Die Sprache aller Wörter der Länge drei?
    Sprache: {aaa, aab, aac, aba, abb, abc, aca, acb, acc …} (insgesamt 27 Stück)
    RegEx: (a|b|c)(a|b|c)(a|b|c)
  • Die Sprache aller Wörter mit genau einem a darin?
    Sprache: {bcbcba, a, abbbcccb, bab, bccbab…}
    RegEx: (b|c)*a(b|c)*
  • Die Sprache aller Wörter, in denen maximal zwei verschiedene Buchstaben auftauchen?
    Sprache: {a, b, c, ab, abbaab, cacaac, bcbcbc, bbb…}
    RegEx: (a|b)*|(a|c)*|(b|c)*

Weil reguläre Ausdrücke auf diese Weise schnell umständlich werden können, gibt es viele verschiedene Abkürzungen (wie . für “beliebiges Zeichen”), die man aber alle auf die oben verwendeten zurückführen kann.

2. Reguläre Grammatiken

Eine reguläre Sprache kann man statt durch einen regulären Ausdruck auch durch eine reguläre Grammatik beschreiben. Machen wir es uns einfach: Das Alphabet sei {a, b}, die Sprache sei durch ab(bb)*a beschrieben. Die Sprache ist demnach {aba, abbba, abbbbba…}, jedes Wort besteht aus einem a und danach einer ungeraden Zahl an b’s, gefolgt von einem schließenden a.

Die Regeln der Grammatik:
1. S => aA
2. A => bB
3. B => a
4. B => bC
5. C => bB

S ist der Startpunkt, Großbuchstaben sind hier sogenannte Nichtterminale (also quasi Namen von weiteren Ableitungsregeln), Kleinbuchstaben sind Terminalzeichen (Zeichen des Alphabets, hier also nur a oder b). Man fängt bei S an. Alles, was links vom Pfeil steht, kann man durch das ersetzen, was rechts davon steht. Regel 2 sagt also, dass man jedes irgendwo auftauchende A durch bB ersetzen kann.
Eine Ableitung ist dann abgeschlossen, wenn sie nur noch aus Terminalzeichen, also Buchstaben des Alphabets, besteht (hier a und b).

Zum Beispiel:

aba entsteht durch die Regeln 1, 2, 3:
S => aA, => abB, => aba

abbba entsteht durch die Regeln 1, 2, 4, 5, 3:
S => aA, => abB, => abbC, => abbbB, => abbba

abbbbba entsteht durch die Regeln 1, 2, 4, 5, 4, 5, 3:
S => aA, => abB, => abbC, => abbbB, => abbbbC, =>abbbbbB, =>abbbbba

Eine (rechts-)reguläre Grammatik erfüllt folgende Bedingungen:

  • Links vom Pfeil steht immer nur ein einziges Nichtterminalzeichen.
  • Rechts vom Pfeil steht entweder gar nichts (dargestellt durch ein ε), oder genau ein Terminalzeichen, oder genau ein Terminal gefolgt von genau einem Nichtterminal.

Man sieht an der Ableitung der drei Wörter oben gut, das bei einer regulären Grammatik das Wort einzelner Buchstabe für einzelner Buchstabe von links nach rechts aufgebaut wird. Die Regeln für diesen Grammatiktyp sind so beschaffen, dass das immer so ist. Ein Wort, das 6 Zeichen lang ist, wird immer in 6 Schritten abgeleitet.

3. Endliche Automaten

Und zuletzt kann man eine reguläre Sprache auch durch einen endlichen Automaten beschreiben. Der Automat, der sich auf dieselbe Sprache bezieht wie ab(bb)*a, sieht so aus:

automat

Wenn man ihn richtig liest, sieht man gleich die Parallelen zu der oben angegebenen Grammatik. Die Kreise geben verschiedene Zustände an, in denen sich der Automat befindet. Man kann mit dem Automaten prüfen, ob zum Beispiel das Wort “aba” von ihm akzeptiert wird.
Man beginnt immer dort, wo der Pfeil ist, hier also beim Zustand (S). Dann nimmt man sich den nächsten (ersten) Buchstaben vor, ein a, man folgt der Beschriftung der Pfeile und landet im Zustand (A). Kommt dann das b, geht man zu (B). Kommt dann das (letzte) a, landet man bei ((Z)). Da danach kein Buchstabe im Wort mehr kommt, hört man auf und schaut, ob man auf einem “akzeptierenden” Zustand steht. Das sind die mit den zwei Kreisen drumrum. In dem Automaten oben ist nur ((Z)) akzeptierend. Und ja, wir sind in diesem Zustand, also wird aba akzeptiert.

Ein Wort wird dann nicht akzeptiert, wenn der Automat in einem der anderen, nicht akzeptierenden Zustände stehen bleibt – S, A, B, C oder X. Das Wort abbb landet zum Beispiel bei (B), das Wort abb bei (C) und die Wörter abba, ba und abbbab, abbbaa alle bei (X). (X) ist in diesem Beispiel übrigens ein langweiliger Zustand, den der Automat nie wieder verlassen wird. Er steht quasi für “endgültig falsch, da wird nichts mehr draus”. Ich habe alles, was ihn betrifft, mal nur mit Bleistift eingezeichnet.
Bei einem Wort, das 6 Zeichen lang ist, weiß man immer nach genau 6 Schritten, ob es akzeptiert wird oder nicht.

Endliche Automaten heißen so, weil man sie vollständig auf ein Stück Papier malen kann. Man kann mit ihnen aber unendlich viele und unendlich lange Wörter basteln.

Typische Aufgaben aus dem Studium: Zu einer gegebenen regulären Sprache den regulären Ausdruck finden, die reguläre Grammatik oder den Automaten dazu, oder umgekehrt. (Oder beweisen, dass eine gegebene Sprache regulär ist.)

3. Das Wortproblem für reguläre Sprachen

Das Wortproblem wird später noch einmal wichtig. Es lautet: Kann man einen Algorithmus bauen (also zum Beispiel einen solchen Automaten), der für jedes beliebige Wort zu einem gegebenen Alphabet in endlicher Zeit entscheidet, ob das Wort zu einer bestimmten Sprache gehört oder ob es nicht dazu gehört? Für reguläre Sprachen: ja. Das Wortproblem für solche Sprachen ist “entscheidbar”. Sogar recht schnell: Bei einem Wort der Länge n braucht man n Schritte, und man hat die Antwort – die Bestätigung oder die Ablehnung.

4. Zusammenfassung

Mit einem regulären Ausdruck kann man sehr viele sehr verschiedene Wörter auf einmal beschreiben, nämlich alle, die zu einer bestimmten regulären Sprache gehören. (Dazu gibt es alternativ eine reguläre Grammatik oder und einen entsprechenden Automaten.) Allerdings geht noch lange nicht alles. Schon so etwas Simples wie “alle Wörter, die genauso oft den Buchstaben a wie den Buchstaben b enthalten” geht mit keiner dieser Methoden. Denn die Sprache, die aus allen diesen Wörtern besteht, ist keine reguläre Sprache. Sie gehört zum Chomsky-Typ 2, einer kontextfreien Sprache.

Mehr dazu, und warum das überhaupt wichtig ist, beim nächsten Mal.

Nachtrag: Ein weiteres Beispiel ist mir eingefallen, das vielleicht nützlich ist. Man nimmt sich ein Wörterbuch und sucht mit einem RegEx nach allen Palindromen darin, also allen Wörtern, die vorwärts und rückwärts gleich gelesen werden. Wäre schön, wenn’s ginge. Geht aber nicht. Auch die Sprache, die aus allen Palindromen besteht, ist Chomsky 2.

Freiwillige Hausaufgabe für Einsteiger:

Welche Wörter akzeptiert der folgende Automat? Welcher reguläre Ausdruck beschreibt dieselbe Sprache? Es gibt drei Zustände {S, B, X}, der Startzustand ist S, akzeptierend ist nur B. Das Alphabet ist wieder nur {a, b}.

automat2

Und ein letzter Tipp:

Wer die Konstruktion endlicher Automaten und das Umbauen von regulären Ausdrücken zu solchen – oder umgekehrt – üben möchte, und das können fast nur Informatiker sein, dem sei dieses wirklich gute Programm empfohlen: Exorciser. Läuft unter Java, ohne Installation.

Teil 3 folgt.

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.

“Night of the Living Dad”

Heute als Podcast gehört, und der Titel ist so gut, dass ich ihn übernehmen muss. Den Artikel von William Saletan kann man ganz bei Slate lesen.

Die Kurzfassung: Das amerikanische Verteidigungsministerium interessiert sich für “a highly interactive PC or web-based application to allow family members to verbally interact with virtual renditions of deployed Service Members.” Die Anwendung soll es Familienmitgliedern, zum Beispiel dem vierjährigen Sohn zu Hause, erlauben, mit einer simulierten Mutter zu kommunizieren. Die Mutter wird eingescannt oder abgefilmt, spricht einige oder auch viele Sätze aufs Band, und die Software macht dann einen Avatar daraus, mit dem man kommunizieren kann, auch ohne dass der Mensch dahinter steckt.

The child should be able to have a simulated conversation with a parent about generic, everyday topics. For instance, a child may get a response from saying ‘I love you’, or ‘I miss you’, or ‘Good night mommy/daddy.’

(Alle Zitate siehe Slate-Artikel.)

Das hat mich gleich sehr an Eliza und ihre Verwandten (“Parry meets the Doctor”) erinnert. Diese Programme bemühten sich gar nicht um künstliche Intelligenz, sondern nur um eine simulierte Konversation. Und man merkt natürlich schnell, wenn auch nicht so schnell, wie man meint, dass Eliza ein Computerprogramm ist und kein Mensch. Aber ich habe nicht mitgekriegt, dass es neuere Programme gibt, die das nennenswert besser können. Sonst wäre mir das doch mal bei einem Computerspiel begegnet, aber da laufen alle Dialoge mit Nichtspielerfiguren extrem unflexibel ab.

Als nächster Schritt, so Saletan, ist dann zu erwarten, dass die Kinder nicht nur mit abwesenden Vätern, sondern auch mit verstorbenen reden können. Und irgendwann wird das Produkt dann zivil verwendet werden, wie es bei vielen militärischen Entwicklungen geschehen ist. (Bei Teflon übrigens nicht.) Saletan glaubt, dass es dafür einen Markt gibt.

Schöner Text, würde ich gerne mit Schülern machen.

Material zu VERA 8

Wir erinnern uns, das sind schon wieder Tests, auf die sich Schüler nicht inhaltlich vorbereiten sollen.

(Fußnote: Bin beim Weihnachtseinkauf erschrocken. Harmlose Physik- und ähnliche Experimentierkästen haben jetzt den Aufdruck “Natur- und Technik. Passend zum Lehrplan der 5.–7. Klasse”. In diesen Jahrgangsstufen gibt es nämlich dieses Zwitterfach aus Bio, Physik und Informatik. Also ein Tritter-Fach, aber das klingt blöd.)

Freunde der klingonischen Oper

Heute nacht um 0:05 Uhr auf Deutschlandradio Kultur: juHrop (“tschuh-rop”, dt. Heimweg), eine Klingonische Oper von Frieder Butzmann. Via netzpolitik.org, zu Details siehe dort. Ja, es ist genau das, an das man denkt.

(Außerdem wird auf Bayern 2 um 21.30 Uhr die erste Folge von Jonas, der letzte Detektiv wiederholt. Die ersten 6 Folgen werden immer am ersten Mittwoch des Monats ausgestrahlt. Hat mir ein Schüler heute zugesteckt.)

Schulanfang 2009

Erster Schultag. Alle, die ich gesehen habe, waren wohlauf, aber ich habe noch nicht alle gesehen. Das Schulgebäude saukalt heute. Heizen ist wohl nicht in den Ferien.

Arbeitsmaterial eines Schülers zu sehen gekriegt. Die 37 Lücken waren in keinem Fall mit den eigentlich einzusetzenden französischen Wörtern gefüllt, stattdessen war in jede Lücke ein kleiner Penis gemalt. In allen möglichen Formen und Größen. Klar, der Schüler hat Probleme, und man wird sich darum kümmern. Das soll hier nicht Thema sein. Aber faszinierend war dieser Katalog schon auch irgendwie. Wirklich alle verschieden.

Beim Drüberschauen über die Schulaufgabe einer Referendarin ist mir folgender Gliederungsausschnitt aufgefallen:

2.1 Nathan als toleranter, selbst denkender Mensch
2.1.1 Nathans Unvoreingenommenheit gegenüber Religionen
2.2 Der Patriarch als Beispiel für Intoleranz und Machtstreben

Die Referendarin hat, genauso wie ich es getan hätte, drunter geschrieben: “Nie nur ein Unterpunkt!” Das ist nämlich eine eiserne Regel für Gliederungen. Wer 2.1.1 sagt, der muss auch 2.1.2 sagen, weil, so sagt man dann, sonst hätte man das ganze ja gleich unter 2.1 zusammen- und es dabei belassen können.

Das sehe ich auch ein. Andererseits, wenn ich Gedanken sammle und hierarchisiere, in einer Liste im Textverarbeitungsprogramm oder in einem ja ebenfalls streng hierarchischen Mindmap-Programm, dann kommt es auch oft vor, dass ich nur einen Unterpunkt habe. So wie es Tiergattungen mit nur einer einzigen Art gibt. Weil es systematisch so passt und weil man so offen für Ergänzungen ist. Sind wir Deutschlehrer da zu kleinlich?

– Ganz zu schweigen von den verschiedenen Gliederungsarten. Kommt nach 2.1.1 jetzt ein Punkt oder nicht? Ist mir ziemlich egal. Wie wichtig ist es, ob nach A) ein I. oder ein 1. kommt? Eigentlich nicht sehr, aber es stört mich trotzdem, wenn’s jemand falsch macht.

Exquisite Weihnachtsgeschenke

(Aus der Reihe: Alles muss raus. Blogbeiträge des Jahrs 2008 aufräumen.)

Von meinen zwei Brüdern und deren Frauen habe ich dieses Jahr jeweils ein Buch zu Weihnachten gekriegt. Bücher, und das mir! Von beiden Büchern hatte ich noch nie gehört, und beide waren überraschend gelungene Geschenke.

Reading the Oxford English Dictionary von Ammon Shea. Penguin 2008.

shea_reading_oed

Ein Erlebnisbereicht. Shea ist ein Wörterbuch-Aficionado, und macht sich an den dicksten Fisch von allen: Das Oxford English Dictionary. 20 Bände. Ein Jahr, Seite für Seite. Das OED unterscheidet sich von anderen englischen Wörterbüchern dadurch, dass es versucht, jedes englische Wort aufzuführen, das es seit Beginn der englischen Sprache gegeben hat. Und es versucht, bei jedem Wort die Fülle an Bedeutungen seit dessen Existenz aufzuführen. Dazu gehören auch viele Beispiele und Zitate, vor allem natürlich Erstbelege für das Auftreten des Worts.

Das Buch selber enthält ein Kapitel für jeden Buchstaben des Alphabets. Vorangestellt sind jeweils einige wenige Seiten darüber, warum man das OED liest, was es dabei für Probleme und Überraschungen gibt, und weitere Wörterbuchkunde und ‑anekdoten. Welche Wörter leicht zu definieren sind und welche schwer. (Fast ergreifend seine Ausführungen zum Wort set.) Shea beschreibt nachvollziehbar, wie die vielen Wörter ihn verwirren. Wie er zum Wort “glove” kommt, wie es ihm völlig unvertraut erscheint und er sich wundert, dass es für einen solchen alltäglichen Gegenstand keinen üblichen Ausdruck gibt.
Davon hätte ich mir mehr gewünscht, aber vielleicht gibt es nicht so viel zu sagen dazu. Den Hauptteil der Kapitel machen dann jeweils kommentierte Fundstücke aus dem OED aus.

  • Bei coenaculous (adj.) ist das schönste seine kopfschüttelnde Vermutung, an manchen Tagen müsse in der Redaktion wohl “casual-definition Friday” gewesen sein.
  • Neu war mir, dass es tatsächlich auch curtain-lecture (n.) gibt, und zwar ganz im Sinn der deutschen Gardinenpredigt. Und das mindestens schon 1755 bei Samuel Johnson.
  • Bizarr ist hot cockles (n.): “A rustic game in which one player lay face downwards […], and being struck on the back by the others in turn, guessed who struck him.” Rustic indeed.
  • Micturient (adj.): das Gefühl haben, dringend pinkeln zu müssen. Cacaturient kriegt allerdings keinen eigenen Eintrag.

Und ja, das Buch macht Lust darauf, das OED zu lesen. Es gibt eine Windows- und eine Online-Ausgabe, und natürlich die 20 Bände selber. Es müssten wohl schon die sein. Aber die sind teuer, und vor allem: Sie nehmen viel Platz weg, den ich nicht habe. Ich bin schon froh, meine 33 Bände Grimmsches Wörterbuch (DWB) losgeworden zu sein. Im Moment ruhen sie beim Kollegen Z., der ihnen aber langfristig auch keinen Platz geben wird. Aber er findet, und da hat er recht, dass jeder Deutschlehrer zumindest mal ein Jahr lang damit leben sollte. Danach könnte es so eine Art Wanderpokal werden. Der Deutschlehrer, der seine Schulaufgaben als letzter zur Respizienz abgibt, muss sich ein Jahr lang das DWB ins Regal stellen.

Vorab habe ich mir nur eine Best-of-Ausgabe von Dr Johnson’s Dictionary bestellt, herausgegeben von David Crystal.

Denksport Physik. Fragen und Antworten von Lewis C. Epstein. Dtv 2006. (Amerikanisches Original 1979.) 576 Seite.

epstein_denksport_physik

Ein tolles Buch. Mit Denksport an sich hat es nicht viel zu tun, sondern mit Physik. Es enthälte Hunderte von Fragen zu Mechanik, Licht, Wärme und so weiter, alle anschaulich illustriert. Einige davon sind Klassiker: In einem mit Wasser gefüllten Glas schwimmt ein Eiswürfel. Schmilzt dieser, a) steigt dann der Wasserspiegel im Glas, b) sinkt er, oder c) bleibt er gleich? Viele davon sind neu. Angeordnet sind sie in einer gewissen didaktischen Reihenfolge, viele der Aufgaben stellen Verfeinerungen, Verallgemeinerungen oder Sonderfälle der vorangegangenen Aufgaben dar.

Am besten ist man für die Lektüre dieses Buches Teil einer Gruppe von Leute, die schon ein bisschen was von Physik verstehen. Das können auch schon Schüler sein. Den Unterschied zwischen Geschwindigkeit und Beschleunigung sollte man schon vorher wissen. Dann nimmt man sich nach und nach eine Aufgabe vor und diskutiert in der Gruppe, welcher der angegeben Lösungsvorschläge der richtige ist.

(Zum Weiterdiskutieren gibt es zu jedem Teilbereich noch ein paar Dutzend zusätzliche Fragen, die jeweils klein gedruckt, ohne Bilder und ohne Lösungen. Am weitesten komme ich übrigens beim Kapitel “Schwingungen”.)

Noch schnell ein Zoobesuch

(Aus der Reihe: Alles muss raus. Angefangene Blogbeiträge des Jahrs 2008 aufräumen.)

Es gibt ein paar Tiere, bei denen schaue ich immer wieder vorbei. So lebhaft wie neulich habe ich die Vielfraße noch nie gesehen. Vielleicht gefällt ihnen die Kälte.

Vielfraße sind die größten Mitglieder der Familie Marder. Die Männchen werden über 30 Kilo schwer. Ihr Name kommt von “Felsenkatze”, tatsächlich essen sie im Sommer Aas, Beeren, Vogeleier; im Winter machen sie sich aber auch an Rentiere und Elche heran. Für ihre relativ kompakte Größe gelten sie als äußerst zähe, kampfeslustige Tiere.

Und natürlich habe ich nur deshalb angefangen, mich für den Vielfraß zu interessieren, weil er auf Englisch wolverine heißt. Eben, genau daher hat Wolverine von den X‑Men seinen Namen.



Viel friedlicher ist dagegen der Katta (ring-tailed lemur), langjährigen Lesern hier wohlbekannt. Es war eher ein Umhertollen als eine Rangelei, aber trotzdem sehen die folgenden Bilder eher nach choreographierter Straßenprügelei aus.