Formale Sprachen, Teil 2: Reguläre Sprachen

By | 12.1.2009

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“ steht. 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.

14 thoughts on “Formale Sprachen, Teil 2: Reguläre Sprachen

  1. Name (notwendig)

    „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.)“

    Es fehlt das Pumping-Lemma.

  2. sts

    um zu Beweisen das eine Sprache regulaer ist, braucht man kein pumping Lemma, es reicht vielmehr einen Automaten anzugeben der die Sprache akzeptiert bzw einen Grammatik die sie produziert.

    schwieriger ist der Nachweis, dass sie nicht Regulaer ist, da reicht eben nicht zu sagen: „mir ist kein Automat eingefallen“, beim Nachweis dass es keinen gibt ist dann eines der Pumping-Lemmas hilfreich, aber auch nicht noetig, man kann den Beweis auch zu Fuss tun, wie unser Matheprof immer zu sagen pflegte.

  3. Herr Rau Post author

    Pumping-Lemma: Ich neide den exakteren Wissenschaften wie so oft ihre schönen Fachbegriffe. Colourful metaphors indeed. Pumping bezieht sich tatsächlich aufs Aufpumpen.

  4. DJH

    Ich weiß nimmer genau, was das Pumping-Lemma war, ich hab mir nur gemerkt, dass es was war, was ich für ohnehin gegeben angesehen habe. :)

    So lustige typische Aufgaben hatten wir auch in der Vorlesung „Theoretische Informatik“. Aber auch z. B. einen NEA in einen DEA umwandeln, also einen nichtdeterministischen endlichen Automaten in einen deterministischen. Deine Automaten sind alle beide deterministisch. Bei den Nichtdeterministischen Automaten darf man Pfade, die zum Fehlerzustand führen, weglassen, und einige Pfade z. B. auch verdoppeln (also 2 Pfeile mit b weg von einem Zustand). Macht zwar zum Entwerfen weniger Arbeit, aber ist nicht so leicht aus der Grafik zu kapieren. Beim deterministischen muss jedes „Eingabezeichen“ genau einmal vom Zustand wegführen.

    Die Lösung von deiner kleinen Aufgabe ist übrigens /a*ba*/ (als PCRE, Pearl Compatible RegEx).
    Da fällt mir noch ein: Wenn ich mich richtig entsinne, sind die Backreferences, die es in den PCRE gibt, erst in kontextsensitiven Sprachen möglich. Aber gerade das macht die RegEx so toll!

  5. Herr Rau Post author

    Backreferences: stimmt wohl. Aber wenn, dann kontextfrei, vermute ich. Und stimmt, umwandeln hatten wir auch. Bei uns waren aber die englischen Abkürzungen angesagt, also DFA, NFA (und PDA für den Kellerautomat).

  6. Actron

    „Das Wort abbb landet zum Beispiel bei (B), das Wort abb bei (C) und die Wörter abba, ba und abbbab, abbbaa alle bei (F). (F) ist in diesem Beispiel übrigens ein langweiliger Zustand, den der Automat nie wieder verlassen wird.“

    Statt (F) ist hier wohl (X) gemeint!?

  7. Herr Rau Post author

    Stimmt, (F) gibt es ja gar nicht. Ich hab’s ausgebessert, danke.

  8. Pingback: Zwischen Kontextfreiheit und Kontextsensitivität, Teil 1: Crashkurs Simple Range Concatenation Grammars (SRCG) | Texttheater

  9. Schneider

    Schade, Teil III lässt sich gar nicht öffnen!!! Kommt nur eine weisse Fläche … (Linux, Firefox 3.6.15)

    ansonsten super Vorlesung!

  10. Herr Rau Post author

    Tut mir leid, also das mit Teil III. Bei meinem Linux (Firefox 4.0.1) lädt die Seite ganz normal, es ist auch kein besonderer Code drin – kein Java, kein Flash, nur HTML. Vielleicht war’s einfach ein Cache-Problem, also eines auf meinem Server, wo ich die meisten Wordpress-Seiten gecacht anbiete. Vielleicht beim nächsten Mal?

    – Nachtrag: gerade habe ich eine falsche HTML-Verschachtelung in III gefunden und aufgelöst. Vielleicht lag es auch daran.

  11. Ulrich Koch

    Nö, Backreferences erlauben auch nicht-kontextfreie Sprachen.
    Einfache Aufgabe: Perl-Regex für {ww | w in {a,b}*}.

  12. Sinan A.

    Das ist wirklich PERFEKT erklärt!!!!
    iCH DANKE FÜRS PERFEKTE TUTORIAL******

  13. gastHier

    Wie ist denn die korrekte Lösung für die letzte, „freiwillige Hausaufgabe“?
    Hab eine evtl. Lösung:
    RegEx: a*ba*
    Grammatik:
    S -> aS | bB | b
    B -> aB | bX | a
    X -> aX | bX

    Nicht auslachen, wenn es falsch ist ;)
    Gruß

  14. Herr Rau Post author

    Stimmt alles. Nur die letzte Zeile (und das bX in der Zeile davor) sind überflüssig, da man, wenn man einmal mit dem X angefangen hat, nie mehr dazu kommen wird, dass die Zeichenkette nur noch aus Terminalen besteht, dass die Ableitung (eines Wortes) also beendet wird.

    Der Automat, wenn er vollständig sein soll, auch wenn man das oft nicht verlangt, braucht das X. Die Grammatik braucht es nicht, da sie Wege in Sackgassen gar nicht erst anbieten muss.
    (Der Automat überprüft ja gegebene Zeichenketten, und da kann es eben schon mal sein, dass ein Zeichen ihn in den X-Zustand führt. Die Grammatik produziert nur Zeichenketten, und zwar nur legale, die zu der Sprache gehören.)

Schreibe einen Kommentar

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