Reguläre Sprachen, reguläre Ausdrücke

von Helmut Richter

Die Begriffe „reguläre Sprache“ und „regulärer Ausdruck“ werden erläutert. Dabei werden sowohl theoretische als auch programmiertechnische Aspekte beleuchtet.

Diese Veröffentlichung im Web erfolgt durch den Verfasser. Zuvor war derselbe Inhalt seit etwa 2004 bis März 2025 als Schulungsunterlage unter dem URL https://www.lrz.de/services/schulung/unterlagen/regul/ auf dem Webserver des Leibniz-Rechenzentrums der Bayerischen Akademie der Wissenschaften (LRZ) öffentlich zugänglich.

Inhalt

Über diesen Artikel

Wer sich in die Benutzung von Programmierwerkzeugen wie der Scriptsprache perl oder der auf Unix-Systemen vorhandenen Programme grep oder awk einarbeiten will, sieht sich mit dem Begriff „regulärer Ausdruck“ konfrontiert, der dem Normalbürger in der Regel unbekannt ist. Informatiker, also nicht ganz so normale Bürger, kennen diesen Begriff aus der Theorie der formalen Sprachen im Zusammenhang mit „regulären Sprachen“ und „endlichen Automaten“. Was verbirgt sich nun dahinter?

Dieser Artikel hat das Ziel, einen Leitfaden durch die verwirrende und widersprüchlich gebrauchte Begriffswelt zu bieten.

Der erste, mehr programmiertechnische Teil geht hinsichtlich der Notationen in den verschiedenen Programmen stark ins Detail und unterscheidet sich so von dem eher feuilletonistischen zweiten Teil. Wichtig war dabei, Ähnlichkeiten und Unterschiede zwischen ähnlich aussehenden Konstrukten herauszuarbeiten. Um also ein bestimmtes Werkzeug benutzen zu können, ist das möglicherweise der falsche Ansatz. Vielmehr sollen dem Leser Orientierungspunkte an die Hand gegeben werden, mit denen er sich in der verwirrenden Vielfalt zurechtfinden kann.

Der mehr theoretische Teil (der erst im Entstehen ist) soll nicht Bücher oder Vorlesungen über formale Sprachen ersetzen, sondern möglichst schlaglichtartig beleuchten, worauf es in dieser Theorie ankommt und was ihre besondere Schönheit ausmacht. Ganz entgegen den Gepflogenheiten der Mathematiker wird dabei fast ganz und gar auf formale Definitionen, Sätze und Beweise verzichtet. Damit dürften diese Teile für ein breiteres Publikum lesbar werden.

Muss man das alles lesen?

Nein. Dieser Artikel versteht sich eher als eine Art Enzyklopädie, wo man immer nur das liest, was einen gerade interessiert. Die verschiedenen Abschnitte bauen auch nicht alle aufeinander auf, so dass eine selektive Lektüre durchaus möglich ist. Hier sind ein paar mögliche Pfade durch diesen Artikel für Leser mit unterschiedlichen Interessen:

Was sind reguläre Sprachen und reguläre Ausdrücke?

Egal, ob Theorie oder Programmierpraxis, wir haben es in jedem Fall mit formalen Sprachen zu tun, wobei hier unter Sprache einfach eine Menge von Zeichenreihen (auch Strings genannt) verstanden wird, die ihrerseits wieder aus Zeichen bestehen, die einem Alphabet angehören. Die Zeichenreihen, die zu einer Sprache gehören, werden oft Wörter, manchmal (hier aber nicht) auch Sätze der Sprache genannt; das hat nichts damit zu tun, was diese beiden Begriffe im Zusammenhang mit natürlichen Sprachen bedeuten.

Formal heißen die Sprachen, um sie von natürlichen Sprachen zu unterscheiden. Außerdem geht es hier ausschließlich um syntaktische Fragen, also Fragen, die sich auf die Gestalt der Zeichenreihen beziehen, wie „Gehört diese Zeichenreihe zur Sprache?“ oder „Kommt in dieser Zeichenreihe ein Muster vor, auf das diese Beschreibung passt?“. Semantische Fragestellungen, also solche, die sich auf die Bedeutung der Zeichenreihen beziehen, spielen hier keine Rolle.

Nehmen wir als Beispiel diejenigen Zeichenreihen, die ganze oder Dezimalzahlen in der üblichen deutschen Notation darstellen. Verbal ließen sich diese etwa so beschreiben:

In der Programmierung kann man das mit einem regulären Ausdruck so notieren:

[+-]?[0-9]+(,[0-9]+)?

Die Einzelheiten, was das bedeutet, werden später erläutert, z.B. das Fragezeichen, das einen Teilausdruck markiert, der vorhanden sein kann, aber nicht muss.

Eine Sache sorgt anfangs immer wieder für Verwirrung, nämlich die Endlichkeit oder Unendlichkeit der ganzen Angelegenheit. An dem Beispiel eben kann man sich das klarmachen:

Also: Reguläre Ausdrücke dienen dazu, Sprachen, d.h. Mengen von Zeichenreihen zu beschreiben. Je nachdem, wie dabei die regulären Ausdrücke definiert sind, kann man damit eine bestimmte Sprache beschreiben oder auch nicht. Das Beispiel oben lässt sich mit allen Varianten regulärer Ausdrücke beschreiben, wenn auch die verschiedenen Varianten verschieden aussehen mögen, aber ansonsten ist die Verwirrung groß. Sie lässt sich so zusammenfassen:

Wie lässt sich unter diesen Umständen der Gebrauch, oder besser Missbrauch, des Begriffs „regulärer Ausdruck“ verstehen? Das liegt zunächst einmal an der Geschichte: die regulären Ausdrücke der Theorie waren der Ausgangspunkt für die regulären Ausdrücke in der Programmierung, nur wurden anfangs seltener benötigte, schwerer zu implementierende Eigenheiten weggelassen und später komplexere hinzugefügt. Bis heute ist aber das wichtigste Einsatzgebiet der regulären Ausdrücke in der Programmierung die Erkennung von solchen Mustern in Zeichenreihen geblieben, die in der Tat reguläre Sprachen bilden. Insofern ist die Ähnlichkeit eben doch nicht zufällig.

Reguläre Ausdrücke in der Programmierung

Eine Warnung vorweg: reguläre Ausdrücke werden in der Programmierung nach deutlich verschiedenen Konventionen notiert. Diese lassen sich in mehrere verschiedene „Schulen“ oder „Traditionen“ einteilen; das wird Gegenstand des übernächsten Abschnittes sein. Vorher wird an einem Beispiel gezeigt, wie reguläre Ausdrücke zum Beispiel aussehen können. Damit wird das allen Notationen gemeinsame Prinzip erklärt und nebenbei das Material für die anschließende Diskussion der Gemeinsamkeiten und Unterschiede der Notationen bereitgestellt.

Metazeichen und andere Zeichen

Um zu verstehen, wie in der Programmierung reguläre Ausdrücke notiert werden, wenden wir uns noch einmal dem Beispiel vom Anfang dieses Artikels zu:

[+-]?[0-9]+(,[0-9]+)?

Dabei fällt auf, dass es hier offensichtlich zwei Arten von Zeichen gibt:

Wer den Umgang mit formalen Notationen gewohnt ist, etwa aus der Mathematik, wird keine Schwierigkeiten haben, den Ausdruck oben in seine Bestandteile zu zerlegen und entsprechend zu verstehen. Für die anderen wird hier noch detaillierter dargelegt, wie die ineinander verschachtelten Teilausdrücke zusammenwirken:

Man löst solche Fragen, indem man den Ausdruck strikt in seine Bestandteile gliedert. Das Fragezeichen sagt aus, dass der Teilausdruck  ,[0-9]+  optional ist. Ist im zu untersuchenden String ein Teil vorhanden, der diesem Teilausdruck entspricht, ist es recht, wenn nicht, auch. Wenn ein solcher Teilstring vorhanden ist – und nur dann – interessieren wir uns dafür, wie er aussieht: und dann gibt es Zeichen, die er zwingend enthalten muss.

Jetzt brauchen wir nur noch die Vorrangregeln zu kennen und schon können wir nach Herzenslust reguläre Ausdrücke schreiben. Die Vorrangregeln sind:

Die verschiedenen Notationen für reguläre Ausdrücke

Bei den regulären Ausdrücken erleben wir das Dilemma jeder Normung: wird etwas genormt, bevor es in allgemeinem Gebrauch ist, so ist die Norm weltfremd und wird nicht akzeptiert, ist es aber in allgemeinem Gebrauch, so ist es zu spät für die Normung. Bei Software-Schnittstellen, wie hier eben bei den regulären Ausdrücken, kann eine spätere Normung einen davon abweichenden früher üblichen Gebrauch nachträglich entwerten, was man natürlich vermeiden will. Trotzdem hat man sich bemüht, die unterschiedlichen Notationen für reguläre Ausdrücke zu vereinheitlichen, so dass es nicht beliebig viele, sondern im wesentlichen nur drei verschiedene Notationen gibt. In diesem Abschnitt werden diese drei in ihren Grundzügen dargestellt, im nächsten in etwas mehr Detail, und dann folgt noch eine Übersicht, welche diese Notationen von welchem Programm akzeptiert wird.

Das Hauptproblem bei der Vereinheitlichung der Notation für reguläre Ausdrücke sind die Metazeichen: wird die Notation um zusätzliche Operatoren erweitert, so werden Zeichen, die bisher terminale Zeichen waren, plötzlich zu Metazeichen, ändern also in bestehenden Programmen ihre Bedeutung. Beispielsweise ist das Fragezeichen zur Bezeichnung optionaler Teile erst später dazugekommen, in früheren Programmen gab es das nicht. Mit dieser Neuerung ändert aber jeder reguläre Ausdruck, der zufällig ein Fragezeichen enthält, seine Bedeutung. Man hat nun, je nach Anwendung, drei verschiedene Wege beschritten:

Die im vorangegangenen Abschnitt verwendete Notation war, wie man an der Form der runden Klammern (nämlich ohne Verzierung durch einen inversen Schrägstrich) leicht sehen kann, die der Erweiterten Regulären Ausdrücke. In einer BRE hätte es übrigens weder das Pluszeichen noch das Fragezeichen gegeben – diese Zeichen hat man trotz ihrer Nützlichkeit nicht zu den BREs dazugenommen, weil sie dann nach den BRE-Regeln mit inversem Schrägstrich geschrieben werden müssten, was sehr unübersichtlich wäre.

Während die Notationen ERE und BRE relativ ähnlich sind (weswegen man wohl immer in den Manualen der einzelnen Programme nachschauen muss, welche davon verwendet wird und mit welchen Einschränkungen oder Erweiterungen), unterscheiden sich Shell-Namensmuster von eigentlichen regulären Ausdrücken ganz wesentlich in der Art der Darstellung: Bei den ersteren gibt es ein Metazeichen, den Stern, für einen beliebigen (evtl. auch leeren) String, während es bei ERE und BRE ein Metazeichen mit einer solchen Bedeutung nicht gibt. Der Stern bei ERE und BRE hat seine Bedeutung nämlich nur im Zusammenhang mit dem unmittelbar vorhergehenden Zeichen oder geklammerten Teilausdruck und zeigt dessen Wiederholung an. Um einen beliebigen String als ERE oder BRE darzustellen, wird der Punkt für ein beliebiges Zeichen mit dem Stern für dessen Wiederholung kombiniert.

Beispiel: [ab]* als ERE oder BRE steht für eine beliebige Folge von a und b, z.B. aabbaba; diese Menge erlaubter Strings ist nicht als Shell-Namensmuster darstellbar. [ab]* als Shell-Namensmuster steht für einen beliebigen String, der mit a oder b beginnt; diese Menge erlaubter Strings würde als ERE oder BRE mit dem Ausdruck [ab].* dargestellt.

Außerdem werden auch sonst in Shell-Namensmustern und eigentlichen regulären Ausdrücken unterschiedliche Metazeichen verwendet. Unten in der Tabelle sind die Unterschiede zusammengestellt, wobei der von dieser wichtigen Unterscheidung betroffene Bereich durch gelbe Hintergrundfarbe besonders herausgestellt ist. Man sieht dabei auch, dass sich im Bereich der Dinge, die durch Shell-Namensmuster überhaupt darstellbar sind, EREs nicht von BREs unterscheiden.

Glücklicherweise treten Notationen in der Art von Shell-Namensmustern und eigentliche reguläre Ausdrücke nie miteinander vermengt auf. Man kann sich also darauf verlassen, dass eine Anwendung konsequent einer der beiden Konventionen folgt: keine Anwendung wird etwa den Stern im Sinne von ERE und BRE benutzen, aber ein einzelnes Zeichen mit einem Fragezeichen bezeichnen.

Übersicht über die Notationen

In der nachstehenden Tabelle sind die verbreitetsten Notationen für reguläre Sprachen zusammengestellt, und zwar:

Nicht in dieser Tabelle enthalten sind:

Auf diese Dinge wird später eingegangen.

Theorie ERE BRE Wildcard
Shell SQL
leere Menge ∅ (fehlt) (fehlt) (fehlt) (fehlt)
einzelnes Zeichen a a a a a
Konkatenation (Hintereinanderschreiben) xy xy xy xy xy
Alternative, Vereinigung x | y x | y (fehlt) (fehlt) (fehlt)
Klammer ( … ) ( … ) \( … \) (fehlt) (fehlt)
Rückverweis auf Inhalt der i-ten Klammer (fehlt) (fehlt) \i (fehlt) (fehlt)
einzelnes Zeichen aus endlicher Menge a | b | c [abc] [abc] [abc] (fehlt)
einzelnes Zeichen nicht aus endlicher Menge (fehlt) [^abc] [^abc] [!abc] (fehlt)
beliebiges einzelnes Zeichen (fehlt) . . ? _
beliebiger Text (fehlt) .* .* * %
Kleenescher Abschluss (0…?-fache Wiederholung) x* x* x* (fehlt) (fehlt)
optionaler Teilausdruck (0…1-fache Wiederholung) ( | x) x? (fehlt) (fehlt) (fehlt)
1…?-fache Wiederholung xx* x+ xx* (fehlt) (fehlt)
m-fache Wiederholung (fehlt) x{m} x\{m\} (fehlt) (fehlt)
m…n-fache Wiederholung (fehlt) x{m,n} x\{m,n\} (fehlt) (fehlt)
m…?-fache Wiederholung (fehlt) x{m,} x\{m,\} (fehlt) (fehlt)

Erläuterungen zur Tabelle:

Welches Programm akzeptiert was?

Shell-Namensmuster

Die Shell (damit ist hier und im Folgenden sh, ksh, bash gemeint, für tcsh gelten zum Teil in Details abweichende Regeln) verwendet die Namensmuster-Notation (das ist die, wo der Punkt keine spezielle Bedeutung hat) an folgenden Stellen:

Außerdem haben die Programme find, pax und cpio Argumente, bei denen das Programm eine Suche nach Dateien entsprechend einem Muster durchführt, wobei das Muster in Shell-Notation geschrieben wird. Bei pax ist ausdrücklich spezifiziert, dass die Sonderregel für Dateipfade wie bei der Dateisubstitution ebenfalls gilt. Bei diesen Programmen muss man die Shell daran hindern, eine solche Substitution schon vorab durchzuführen:

find . -name 'abc*' -print

sucht nach allen Dateien, deren name mit abc beginnt und könnte beispielsweise ./abc1, ./abc2 und ./sub/abc als Ergebnis liefern. Demgegenüber würde

find . -name abc* -print

schon von der Shell durch

find . -name abc1 abc2 -print

ersetzt, was erstens syntaktisch falsch ist und zweitens, wenn es zufällig richtig wäre, nach etwas ganz anderem suchen würde.

Eigentliche reguläre Ausdrücke

Die meisten Programme, die reguläre Ausdrücke verarbeiten, richten sich nach den Regeln von Extended oder Basic Regular Expressions. Leider haben fast alle diese Programme Besonderheiten, in denen sie von der Norm abweichen. In der folgenden Tabelle sind nur die wichtigsten davon zusammengestellt; keinesfalls ersetzt die Tabelle die Lektüre des jeweiligen Manuals.

Programm Parameter ERE/BRE/
Shell-Namensmuster		 Besonderheiten
awk   E 2
cpio Operanden Shell-Namensmuster  
csplit Operanden E  
ed   B 1
emacs, xemacs   B/E 2, 3, 4, 8
ex   B 1, 4, 5
expr Operanden B 6
find -name Shell-Namensmuster  
grep ohne -E -e, -f B  
grep -E, egrep -e, -f E  
lex   E 2, 7
more   B  
nl -b ppattern B  
pax Operanden Shell-Namensmuster  
perl   E 1, 2, 3, 4, 7
sed   B 1
vi   B 1, 4, 5

Erläuterung der Besonderheiten:

  1. Mit dem Schrägstrich (in einigen Programmen auch dem Fragezeichen für Rückwärts-Suche) werden die Suchmuster begrenzt; deshalb werden diese beiden Zeichen innerhalb der Suchmuster mit dem inversen Schrägstrich maskiert.

  2. Es gibt weitere mit \ eingeleitete Ersatzdarstellungen von Zeichen, etwa \\ für den inversen Schrägstrich selbst und \a, \b, \f, \n, \r, \t und \v für die ASCII-Steuerzeichen BEL, BS, FF, LF, CR, TAB und VT.

  3. Es gibt neben den unter Punkt 2 beschriebenen, mit dem inversen Schrägstrich eingeleiteten Symbolen weitere solche, insbesondere für Zeichenklassen (z.B. \d für Ziffern, \s für alle Arten Zwischenraum).

  4. Die Stellen, an denen Wörter aneinander grenzen, können beim Suchen bezeichnet werden, z.B. \b für Wortgrenze, \B für keine Wortgrenze, \< für Wortanfang, \> für Wortende, oder eine Teilmenge dieser Konventionen. Einzelheiten bitte im Manual des entsprechenden Programms nachlesen.

  5. Die Tilde ist auch ein Sonderzeichen, das maskiert werden muss.

  6. Der reguläre Ausdruck wird immer links verankert.

  7. Das Programm hat zahlreiche Erweiterungen in den regulären Ausdrücken, die mit seiner Arbeitsweise zusammenhängen. Einzelheiten bitte im Manual nachlesen.

  8. Die Schreibweisen entsprechen BRE; es gibt auch Rückverweise. Zusätzlich gibt es, wie sonst nur bei ERE, den senkrechten Strich zur Bezeichnung von Alternativen, der (in Analogie zu den Klammern) auch mit vorangestelltem inversen Schrägstrich versehen sein muss, um seine besondere Bedeutung zu erhalten.

Maskierung und Mengen von Einzelzeichen

In diesem Abschnitt geht es darum, welche Notation verwendet wird, um ein einzelnes Zeichen darzustellen, und zwar entweder ein bestimmtes oder ein beliebiges aus einem Vorrat verschiedener Zeichen, z.B. eine beliebige Ziffer.

Ein bestimmtes einzelnes Zeichen wird einfach durch sich selbst dargestellt, es sei denn, dass es innerhalb regulärer Ausdrücke eine besondere Bedeutung hat, wie etwa der Punkt (beliebiges Zeichen), der Stern (Wiederholung des letzten Teilausdrucks), die öffnende eckige Klammer (Beginn der Notation einer Menge von Einzelzeichen) oder der inverse Schrägstrich (Maskierung, Beginn einer Klammerung). In diesem Fall muss es maskiert werden. Die einfachste Möglichkeit der Maskierung besteht darin, es in eckige Klammern zu setzen; dadurch wird eine Zeichenmenge definiert, die genau dieses eine Zeichen enthält. Das funktioniert für alle Zeichen, auch die eckigen Klammern selbst, nur nicht für den Zirkumflex-Akzent. Eine Alternative besteht darin, dem zu maskierenden Zeichen einen inversen Schrägstrich voranzustellen; es muss sich dann aber auch wirklich um ein Zeichen handeln, das sonst speziell behandelt würde, während das bei der Maskierung mit der eckigen Klammer gleichgültig ist.

Im Rest dieses Abschnittes geht es um eine vereinfachte Darstellung von Mengen einzelner Zeichen. Gemäß der ERE-Syntax kann man zwar die Sprache „eines der Zeichen a, b oder c“ als (a|b|c) darstellen, aber spätestens bei der Sprache „ein Buchstabe aus dem Bereich von a bis z“ wird diese Darstellung unhandlich und man greift lieber zu der abgekürzten Form [a-z]. Gemäß der BRE-Syntax ist dies sogar die einzige Möglichkeit, da der senkrechte Strich, mit dem Alternativen notiert werden, dort nicht existiert.

Innerhalb der eckigen Klammer verlieren die meisten Zeichen ihre besondere Bedeutung, die sie sonst in regulären Ausdrücken haben. Dafür gibt es leider auch Zeichen, die hier eine besondere Bedeutung erlangen:

Man bekommt beim Aufbau der Liste also keine Probleme, wenn man die Zeichen wie folgt anordnet:

Wenn die Liste fertig ist, kommt ein Zirkumflex-Akzent davor, wenn der Ausdruck die Zeichen darstellen soll, die nicht in der Liste vorkommen. Am Schluss kommen die eckigen Klammern drum herum.

Jetzt kann nur noch der etwas falsch machen, der meint, einen Bereich von Zeichen mit dem Bindestrich oder einer eckigen Klammer beginnen oder enden lassen zu müssen, aber der muss dann eben selbst in die Norm schauen, wie sein kryptischer Ausdruck verstanden wird.

Welche Zeichen in einem Bereich liegen, der mit Bindestrich notiert wird, richtet sich nicht nach der Codierung (etwa im ASCII- oder ISO8859-1-Code), sondern nach der Sortierreihenfolge, die systemweit oder benutzerspezifisch nach den Gepflogenheiten einzelner Länder eingestellt sein kann. Es ist also nicht von vorneherein klar, ob etwa das scharfe ß im Bereich [a-z] enthalten ist oder nicht. Spezifiziert man explizit die POSIX Locale durch Setzen der Environment-Variablem LC_COLLATE auf den Wert POSIX, so liegen wenigstens die Zeichen des ASCII-Codes in der durch diesen Code spezifizierten Reihenfolge; über die übrigen Schriftzeichen schweigt sich die Norm allerdings aus.

Kennt man Sortierreihenfolge und Zeichenklassen der eingestellten Locale (dieses Wort, das „Schauplatz“ bedeutet, spricht sich mit langem [a] ähnlich wie im deutschen Wort „Lokal“), so gibt es weitere Darstellungen von Zeichenmengen wie etwa

Dies hier im einzelnen zu erläutern, würde zu weit führen. Die letzte Möglichkeit könnte aber nützlich sein, will man etwa die Menge der Buchstaben explizit länderabhängig festlegen. Es gibt hier:

Zeichenklasse Bedeutung internationale Voreinstellung (POSIX-Locale)
[:alnum:] alphanumerisches Zeichen [[:alpha:][:digit:]]
[:alpha:] Buchstabe [[:upper:][:lower:]]
[:blank:] Zwischenraum Zwischenraum und horiz. Tabulator
[:cntrl:] Steuerzeichen Steuerzeichen ausschließlich Zwischenraum
[:digit:] Dezimalziffer [0123456789]
[:graph:] Schriftzeichen [[:alpha:][:digit:][:punct:]]
[:lower:] Kleinbuchstabe [abcdefghijklmnopqrstuvwxyz]
[:print:] druckbares Zeichen [ [:graph:]]
[:punct:] Satzzeichen []!"#$%&'()*+,./:;<=>?@\^_`{|}~[-]
[:space:] Freiraum alle Arten Zwischenraum, Zeilenwechsel und Tabulator
[:upper:] Großbuchstabe [ABCDEFGHIJKLMNOPQRSTUVWXYZ]
[:xdigit:] hexadekadische Ziffer [[:digit:]A-Fa-f]

Man kann aber nicht voraussetzen, dass diese internationale Voreinstellung in Kraft ist, da sie durch Environment-Variable gesteuert wird, die anders gesetzt sein können. Im Zweifel muss man explizit die Environment-Variable LC_CTYPE auf den Wert POSIX setzen.

Mustersuche

Bisher hat uns nur die Frage beschäftigt, wie ein regulärer Ausdruck eine Menge von Zeichenreihen beschreiben kann. Es ging also um eine reine Ja/Nein-Entscheidung, ob eine Zeichenreihe in der durch den Ausdruck definierten Sprache liegt, wenn zum Beispiel das Filterprogramm grep entscheiden soll, ob die entsprechende Eingabezeile in die Ausgabe übernommen werden soll oder nicht.

Jetzt wenden wir uns der Frage zu, wie wir innerhalb einer längeren Zeichenreihe einen Teil finden und herauspräparieren können, der uns interessiert, wobei wir durch reguläre Ausdrücke sowohl beschreiben, wo wir suchen als auch was uns interessiert. Nehmen wir als Beispiel die Ausgabe des Unix-Kommandos "ls -l abc", die etwa so aussehen könnte:

rw-r----- 1 joeuser staff 580 Feb 25 14:19 abc

Wenn wir einem menschlichen Zuhörer erklären würden, wo hier der Name des Benutzers steht, dem die Datei gehört, könnte diese Erklärung beispielsweise so lauten:

Erst kommen vielleicht ein paar Zwischenräume, dann kommt ein Teil, der nur aus den Buchstaben b, c, d, p, r, s, w und x sowie aus Minuszeichen besteht, dann kommt mindestens ein Zwischenraum, dann mindestens eine Ziffer, dann mindestens ein Zwischenraum, und dann – hier fängt der Teil an, der mich interessiert – kommen Zeichen, die keine Zwischenräume sind und dann – aber das interessiert mich schon nicht mehr – kommt noch ein Zwischenraum …

Genau diese Information kann man dem Programm expr mit Hilfe eines regulären Ausdrucks mitgeben, wobei der interessierende Teil durch die runden Klammern (die in BRE-Syntax mit voranstehendem \ geschrieben werden) gekennzeichnet wird. So würde in diesem Beispiel das Kommando

expr "`ls -l abc`" : ' *[bcdprswx-]* *[0-9][0-9]* *\([^ ]*\) '

als Ergebnis joeuser liefern.

Sucht man dabei nach einem Teilstring, der durch seine Gestalt eindeutig identifiziert ist, so dass man die Umgebung nicht zu beschreiben braucht, so wäre es natürlich, wenn der Ausdruck mit .* beginnen und auch enden würde, ebenso in dem Fall, dass nur eine kleine Umgebung vor und nach dem Teilstring mit herangezogen werden muss. Es hat sich aber als Konvention eingebürgert, dass umgekehrt vorgegangen wird: bei den meisten Programmen, die nach Mustern suchen, z.B. auch bei grep, wird irgendwo im String nach dem Muster gesucht, d.h. das Suchmuster wird implizit vorne und hinten mit .* ergänzt. Nur wenn man das nicht will, muss man explizit am Anfang einen Zirkumflex-Akzent oder am Ende ein Dollarzeichen schreiben, um die Suche auf den Anfang bzw. das Ende der Zeichenreihe zu beschränken; man sagt dann, das Muster sei am linken bzw. rechten Ende verankert. Warum diese Konvention ganz praktisch ist, wird im nächsten Abschnitt diskutiert. Das Programm expr ist insofern besonders inkonsequent, als es implizit das Muster am linken, nicht aber am rechten Ende verankert. Im Beispiel wurde das benutzt: es wurde nämlich spezifiziert, was am Anfang der Zeile vor dem zu extrahierenden Teil steht, nicht aber, was ihm bis zum Ende der Zeile folgt.

Die Möglichkeit, mit Hilfe regulärer Ausdrücke Information aus Texten herauszufischen und später wiederzuverwenden, kommt sehr häufig in der Praxis vor. Beispiele sind:

Mit den Möglichkeiten der Shell, auch wenn sie um Programme wie expr oder grep erweitert sind, kommt man für die beiden ersten Anwendungen nicht weit; man verwendet dann Skriptsprachen wie perl (universell einsetzbar) oder awk (stärker auf den ersten Anwendungsfall beschränkt).

Die in diesem Abschnitt dargestellten Möglichkeiten sind es, die regulären Ausdrücken viele Anwendungsbereiche erschließen, wo es ohne sie sehr viel umständlicher zugegangen wäre. Man versuche etwa, die Analyse der Ausgabezeile von "ls -l" im obigen Beispiel selbst in Pascal oder einer anderen Programmiersprache (in C natürlich ohne Verwendung der Funktion regexp) zu programmieren; das wird um einiges länger und meist auch unübersichtlicher als die Form mit regulären Ausdrücken, so kryptisch diese auf den ersten Blick auch aussehen mag.

Der Preis für diese Bequemlichkeit ist allerdings hoch, auch wenn das den Anwender nicht zu interessieren braucht: durch solche Erweiterungen des Begriffs „regulärer Ausdruck“ ist das Gebiet verlassen worden, in dem die vielen schönen und einfachen Aussagen gelten, die im zweiten, theoretischen Teil dieses Artikels zusammengestellt sind. Insbesondere die wertvolle Eigenschaft, dass man immer deterministisch vorgehen kann, dass also das Programm, das nach einem Muster sucht, nie eine getroffene Entscheidung rückgängig machen muss, gilt hier nicht mehr. Dazu ein Beispiel: Mit

expr abaaababbaababaabaaaababc : '.*\(a*ba*ba*b\)c'

sollen aus dem links vom Doppelpunkt stehenden String die letzten drei b’s vor dem c mit den davorliegenden a’s herausgefunden werden. Bei der Analyse muss nun sowohl am Anfang als auch nach jedem b mit dem Beginn des herauszufindenden Strings gerechnet werden. Jeder dieser Kandidaten ist also noch aktiv, nachdem der nächste schon begonnen hat.

Außerdem ist die Definition nicht eindeutig: es ist in diesem Fall nicht klar, wo der Bereich des .* endet und der des ersten a* beginnt. In der Norm ist das leider nicht eindeutig definiert, so dass verschiedene Implementierungen verschiedene Ergebnisse liefern können. Im nächsten Abschnitt wird das eingehender diskutiert.

Gier (greed)

In manchen Anwendungsprogrammen, die mit regulären Ausdrücke umgehen, zum Beispiel in perl, lässt sich die „Gier“ (engl. greed) regeln, mit der Zeichen von einem Wiederholungsoperator, also einem Stern oder einem Pluszeichen, „verschlungen“ werden. Und zwar arbeiten diese Operatoren normalerweise mit maximaler Gier, können aber gezähmt werden, indem man ihnen ein Fragezeichen anhängt. Welche Wirkung das hat, soll anhand dreier kurzer perl-Skripts gezeigt werden. Das Skript


$s = 'abaaababbaababaabaaaababc';

if ($s =~ /^(.*)(a*ba*ba*b)c$/) {
  print "gieriger Stern\n erste Klammer: \"$1\"\nzweite Klammer: \"$2\"\n\n";
};

if ($s =~ /^(.*?)(a*ba*ba*b)c$/) {
  print "nicht gieriger Stern\n erste Klammer: \"$1\"\nzweite Klammer: \"$2\"\n\n";
};

liefert die folgende Ausgabe:


gieriger Stern
 erste Klammer: "abaaababbaababaa"
zweite Klammer: "baaaabab"

nicht gieriger Stern
 erste Klammer: "abaaababbaabab"
zweite Klammer: "aabaaaabab"

Dieses erste Beispiel zeigt, dass die Eindeutigkeit, die am Ende des letzten Abschnittes schmerzlich vermisst wurde, durch die Möglichkeit, die Gier zu regeln, wiederhergestellt wird. Die Gier (oder ihr Fehlen) geht aber nie soweit, dass ein Wort der Sprache nicht erkannt wird, wenn man es mit weniger (bzw. mehr) Gier hätte erkennen können. Im Beispiel verschlingt also auch ein gieriger Stern nicht etwa das drittletzte b mit, weil das ja noch für die zweite Klammer gebraucht wird, und auch ein bescheidener Stern auf Hungerkur isst trotzdem brav alle überzähligen bs auf.

Keine Gier bedeutet nur, dass der Stern möglichst früh die Mahlzeit einstellt, nicht aber, dass er sie möglichst spät beginnt; das wird durch das zweite Beispiel demonstriert:

$s = 'aaaaaaaaaab';

if ($s =~ /(a*b)/) {
  print " (mit Gier) gefunden wurde: \"$1\"\n\n";
};

if ($s =~ /(a*?b)/) {
  print "(ohne Gier) gefunden wurde: \"$1\"\n\n";
};

mit der Ausgabe:

(mit Gier) gefunden wurde: "aaaaaaaaaab"

(ohne Gier) gefunden wurde: "aaaaaaaaaab"

Der wichtigste Anwendungsfall für die Giervermeidung ist der, dass es wie im folgenden dritten Beispiel darum geht, einen Textteil zu extrahieren, der durch ein Muster an seinem Ende gegeben ist. Dasselbe Beispiel ohne die Möglichkeit der Giervermeidung wird recht kompliziert. Dazu das folgende Beispiel

$s = 'Anfang Inhalt Ende, und noch ein Ende';

if ($s =~ /Anfang(.*)Ende/) {
  print " (mit Gier) zwischen Anfang und Ende steht \"$1\"\n\n";
};

if ($s =~ /Anfang(.*?)Ende/) {
  print "(ohne Gier) zwischen Anfang und Ende steht \"$1\"\n\n";
};

mit der Ausgabe:

(mit Gier) zwischen Anfang und Ende steht " Inhalt Ende, und noch ein "

(ohne Gier) zwischen Anfang und Ende steht " Inhalt "

Bei der Einführung von Ankern (also Zeichen, mit denen im regulären Ausdruck Anfang oder Ende des Textes bezeichnet werden) war gesagt worden, dass man im Grunde auf die Anker verzichten könnte, wenn man stattdessen bei einer Suche an beliebiger Stelle im Text den uninteressanten Teil explizit mit .* angeben würde. Für die bloße Entscheidung über das Vorliegen eines Musters ist das richtig, für die Mustersuche nicht: würde man diese Angabe machen, wäre dieser Stern (je nach Anwendung) möglicherweise gierig und man würde das letzte und nicht das erste Vorkommen des Musters im Text finden. Das dürfte auch ein Grund für die Konvention sein: es ist einfacher, die Verankerung am Textanfang durch ein Zeichen explizit zu bezeichnen, als dass man im umgekehrten Fall die Suche irgendwo im Text durch einen möglicherweise komplexen regulären Ausdruck bezeichnen muss, der fast alles wegfressen soll, aber trotzdem nicht in seiner Gier die ersten Vorkommen des Suchmusters gleich mitverschlingen darf.

Rückverweise

Im vorletzten Abschnitt haben wir gesehen, wie man mit Hilfe regulärer Ausdrücke Teilstrings herausschneiden und anderweitig weiterverwenden kann. In den Editoren vi und emacs wird das jeweils so formuliert, dass \1 den Teilstring bezeichnet, der bei der Analyse auf den Inhalt der ersten Klammer gepasst hat. Ebenso bezeichnen \2 bis \9 die Inhalte der weiteren Klammerpaare, die dabei in der Reihenfolge des Auftretens jeweils der öffnenden Klammern gezählt werden. Da bietet sich als eine abermalige Erweiterung der regulären Ausdrücke nachgerade an, unter Benutzung derselben Notation einen vorn herausgeschnittenen Teilstring weiter hinten im selben regulären Ausdruck zu verwenden. Beispielsweise bezeichnet dann \(.*\)\1 in BRE-Notation alle diejenigen Strings, die aus zweimal demselben Text bestehen, z.B. aabaaaba.

Wir nehmen wieder das Beispiel vom Anfang des letzten Abschnitts auf, wo mit Hilfe eines regulären Ausdrucks der Name des Dateieigentümers aus der Ausgabe von "ls -l filename" herausgeschnitten wurde. Diesmal verwenden wir diesen Teilausdruck dazu, um im selben Text, noch während der Analyse anhand desselben regulären Ausdrucks, den Namen des Eigentümers mit dem Dateinamen zu vergleichen. Wir können etwa ein ganzes Verzeichnis mit "ls -l" auflisten lassen und dann mit grep diejenigen Zeilen herausfiltern, in denen der Dateiname mit dem Namen des Dateieigentümers übereinstimmt:

ls -l | grep '^ *[bcdprswx-]*  *[0-9][0-9]*  *\([^ ]*\) .* \1$'

Die Stelle, wo der Name bei seinem ersten Auftreten erkannt wird, ist hier in roter Farbe gekennzeichnet und der Abgleich mit dem Namen am Ende der Zeile (also vor dem Anker rechts) in blauer. Dazwischen stehen zwei begrenzende einzelne Zwischenräume und die Zeichenfolge .* für den Teil des Textes, der hier nicht interessiert.

Solche Rückverweise gehören zum Standardrepertoire von BREs, nicht jedoch von EREs; insofern stellen EREs hier trotz ihres Namens keine Erweiterung, sondern eine Einschränkung gegenüber BREs dar. Wir hätten also das Kommando grep nicht zusammen mit der Option -E verwenden können. Der Grund dafür liegt darin, dass nur in BREs sichergestellt ist, dass die Klammer, auf die mit dem Rückverweis Bezug genommen wird, auch tatsächlich zur Analyse verwendet worden ist. Man betrachte etwa die Analyse von abbd mittels des Ausdrucks (ab|c(a*))b\2, wo an der Stelle, an der das d gelesen wird, nicht definiert ist, was \2 bedeutet. Mit BREs tritt dieser Fall wegen der fehlenden Möglichkeit, Alternativen zu spezifizieren, nicht auf. Andere Werkzeuge wie etwa perl erlauben diesen Fall trotzdem; undefinierte Teile sind dort mit dem leeren String vorbesetzt.

Die Warnung am Ende des letzten Abschnittes, man würde das ruhige Fahrwasser der regulären Sprachen hier verlassen, gilt mit solcherart erweiterten regulären Ausdrücken natürlich umso mehr: schon die durch \(.*\)\1 bezeichnete Sprache ist nicht regulär – übrigens nicht einmal kontextfrei –, und das dürfte auch für praktisch alle regulären Ausdrücke gelten, in denen Rückverweise vorkommen, es sei denn, die Ausdrücke in den dazugehörigen Klammern bezeichnen alle nur endliche Sprachen (d.h. sie enthalten keine unbeschränkten Wiederholungen). Außerdem gehört nicht viel Phantasie dazu, sich auszumalen, in wievielfacher Weise es geschehen kann, dass erst am Ende des Textes offenbar wird, worauf man am Anfang etwa hätte achten müssen, so dass der Analysator öfters und sogar in verschachtelten Analyseschritten zurücksetzen muss.

Beispiele

Diese Beispiele sind alle in der ERE-Notation, wenn nicht etwas anderes explizit angegeben ist.

Wortsuche: Schreibungsvarianten, Ausschluss von Zufallstreffern

Mit regulären Ausdrücken kann man nach Wörtern suchen, die in unterschiedlicher Weise geschrieben werden: (Ph|F)otogra(ph|f)ie, Känguruh?, internationali[sz]ation, Schwein[se]braten, Schifff?ahrt, (E|Ae|Ä)ther, Mo[çcsz]ambi(k|que). Wie das letzte Wort zeigt, darf man dabei umso großzügiger auch falsche Schreibungen mit zulassen, je unwahrscheinlicher es ist, andere gültige Wörter zu treffen. Auch eine gleichzeitige Suche nach mehreren Formen eines Wortes unabhängig von Beugungsendungen lässt sich so erreichen:
eine?[mnrs]? geschenkte?[mnrs]? G[aä]ule?s?

Umgekehrt kann man auch versuchen, bei der Suche nach Wörtern mit Hilfe regulärer Ausdrücke falsche Treffer zu eliminieren. Sucht man etwa das Wort nett, so gelten die Treffer Nettopreise, Variablenettikett, Subnetting, Bajonettverschlüssen, nettype, NetTape (alle mit Harvest auf dem LRZ-WWW-Server gefunden) nicht. Man schließt sie aus, indem man ein wenig Kontext mitgibt, etwa mit einem Kommando wie:

grep -Ei '(^|[ (])nett([^aoy]|$)' Dateiname

Die erste Klammer im regulären Ausdruck beschränkt die Suche darauf, den String nett nur am Anfang eines Wortes zu suchen: ganz am Textanfang (durch ^ als Anker dargestellt), nach einem Zwischenraum oder nach einer öffnenden Klammer (dem einzigen Satzzeichen, das üblicherweise ohne Zwischenraum vor einem Wort steht). Mit der zweiten Klammer sollen die zufälligen falschen Treffer ausgeschlossen werden; auch hier darf man den Fall nicht vergessen, dass das Suchwort unmittelbar am Textende steht, was für grep ja jedes Zeilenende ist. Im Gegensatz zur Verbreiterung der Suche lässt sich eine zweckmäßige Einschränkung nur selten vorher ausknobeln: man ermittelt sie durch Versuch und Irrtum.

Texte, die an ihrem Anfang und ihrem Ende erkannt werden

Eine häufige Anwendung regulärer Ausdrücke sind solche Texte, bei denen man zwar wenig über den Inhalt weiß, aber durchaus etwas über Anfang und Ende. Das erste Beispiel dafür sei ein beliebiger Text in runden Klammern. Der auf den ersten Blick naheliegendste reguläre Ausdruck dafür ist

[(].*[)]

Man beachte die Notwendigkeit, die Klammern durch einen vorangestellten inversen Schrägstrich oder wie hier durch Einschluss in eckige Klammern zu maskieren. Dieser Ausdruck ist so unmittelbar einleuchtend, dass man gar nicht ahnt, welche Tücken er enthalten kann:

Wegen dieser immer lauernden Gefahr sollte man es sich daher angewöhnen, in solchen Fällen immer die nur unwesentlich komplexere Form

[(][^()]*[)]

zu wählen, mit der im eingeklammerten Text selbst keine öffnende oder schließende Klammer stehen darf, so dass man immer ein zusammengehöriges innerstes Klammerpaar erwischt. Besteht das Endezeichen allerdings aus mehreren Zeichen, kann das leider beliebig umständlich werden. Ist etwa der Text zwischen Anfang und Ende eingeschlossen, so müsste man eigentlich den regulären Ausdruck so schreiben:

Anfang([^E]|E[^n]|En[^d]|End[^e])*(E(nd?)?)?Ende

Der mit dem Stern wiederholte Teil akzeptiert nicht ganz alle Texte, die das Wort Ende nicht enthalten: wie man leicht sieht, ist z.B. En nicht dabei, und der String AnfangEnEnde würde ohne den eingeschobenen Teilausdruck (E(nd?)?)? nicht richtig erkannt.

Oft kann man da an der Präzision Abstriche machen, wenn klar ist, dass bestimmte Texte im Inneren nicht vorkommen. In Skripten sollte man aber immer den allgemeinsten Fall berücksichtigen: sie werden manchmal nach Jahren für einen anderen Zweck verwendet, wo eine stillschweigend vom ersten Programmierer eingebaute Voraussetzung nicht mehr erfüllt ist.

Fein heraus ist man in solchen Fällen, wenn das Anwendungsprogramm es gestattet, festzulegen, dass der Wiederholungsoperator seine Gier zügeln soll, mit der er Text verschlingt.

Einfach maskierter Text

Nehmen wir als Beispiel eine E-Mail-Adresse, bei der der wirklich relevante Teil in spitze Klammern eingeschlossen ist (darüber hinaus gibt es weitere erlaubte Schreibweisen für E-Mail-Adressen, die jetzt nicht interessieren, siehe RFC822). Also etwa so:

LRZ-Hotline <hotline@lrz.de> (Return requested)

Ein regulärer Ausdruck dafür könnte einfach so aussehen:

.*<.*>.*

Hier durfte man, im Gegensatz zum vorangegangenen Abschnitt, die unbekannten Teile einfach mit .* bezeichnen, da ja genau ein < und ein > vorkommen müssen. Es ist allerdings erlaubt, diese beiden Zeichen auch sonst vor, zwischen und nach dem spitzen Klammernpaar zu verwenden, wenn sie dort durch Einschluss in Anführungszeichen maskiert sind. Ein regulärer Ausdruck, der dem Rechnung trägt, ist ganz einfach zu realisieren: Der Punkt in .* muss durch etwas ersetzt werden, was neben einzelnen Zeichen auch maskierte Zeichenreihen enthält, nämlich durch [^"<>]|"[^"]*" (ein harmloses Zeichen oder ein in Anführungszeichen eingeschlossener Text). Damit wird der oben angegebene Ausdruck zu

([^"<>]|"[^"]*")*<([^"<>]|"[^"]*")*>([^"<>]|"[^"]*")*

Das sieht schlimm aus, aber nur für den, der bei der Entstehung nicht dabei war.

Mehrfach maskierter Text

Gibt es mehrere Möglichkeiten der Maskierung in der Weise, dass sich die zur Maskierung eingesetzten Zeichen sogar gegenseitig maskieren können, kann die Erstellung eines regulären Ausdrucks wie im letzten Beispiel schnell unübersichtlich werden. Als Beispiel soll nun ein regulärer Ausdruck für alle jene Unix-Kommandozeilen konstruiert werden, bei denen alle mit Apostroph oder Anführungszeichen begonnenen Texte ordnungsgemäß abgeschlossen sind. Im einzelnen gelten dafür die folgenden Regeln:

Die Aufgabe kann man durchaus in derselben Weise zu lösen versuchen wie die vorige. Viel besser ist es aber, systematisch vorzugehen und sich alle Möglichkeiten aufzuschreiben, wie die verschiedenen Maskierungszeichen aufeinander einwirken. Nur: mit einer solchen Tabelle kommen wir bei unserem jetzigen Wissensstand nicht weiter. Deswegen wird die Darstellung des vollständigen Lösungsweges in den Theorie-Teil dieses Artikels verlegt und hier nur die fertige Lösung verraten:

([^'"\]|[\].|['][^']*[']|["]([^"\]|[\].)*["])*

Gregorianische Kalenderdaten

Es soll ein regulärer Ausdruck angegeben werden, der genau die Kalenderdaten in der Schreibweise nach ISO 8601 (also Jahr-Monat-Tag mit vierstelligen Jahreszahlen und zweistelligen Monats- und Tagesangaben) beschreibt. Wir konstruieren diesen Ausdruck, indem wir zunächst Variable einführen und diese dann ersetzen, um den fertigen Ausdruck zu erhalten.

V seien die durch vier teilbaren zweistelligen Zahlen außer 00:

V = 0[48]|[2468][048]|[13579][26]

Damit definieren wir S, die vierstelligen Jahreszahlen der Schaltjahre, sowie J, alle Jahreszahlen. Dabei fangen wir mit 1000 an, weil es vorher noch keinen Gregorianischen Kalender gab; dessen genaues Einführungsdatum, den 1582-10-15, berücksichtigen wir nicht. Das soll aber die einzige Vereinfachung bleiben.

S = [1-9][0-9]V|V00
J = [1-9][0-9][0-9][0-9]

M bezeichne alle Monate, N die außer Februar und L die mit 31 Tagen:

M = 0[1-9]|1[0-2]
N = 0[13-9]|1[0-2]
L = 0[13578]|1[02]

T seien die Tageszahlen, die es in jedem Monat gibt:

T = [01][1-9]|10|2[0-8]

Damit definieren wir D, die Daten, die es in jedem Jahr gibt. Das Minuszeichen, das hier auftritt, ist im Gegensatz zu den vorherigen terminal, d.h. es bedeutet nur, dass dort ein Minuszeichen zu stehen hat. Vorher war nämlich jedes Minuszeichen innerhalb einer eckigen Klammer, wo es eine Bedeutung als Metazeichen hatte.

D = M-T|N-(29|30)|L-31

Schließlich erhalten wir alle erlaubten Daten G:

G = J-D|S-02-29

Jetzt setzen wir für die Variablen wieder die zugehörigen regulären Ausdrücke ein:

G =  J-D|S-02-29 =
=  [1-9][0-9][0-9][0-9]-(M-T|N-(29|30)|L-31)|([1-9][0-9]V|V00)-02-29 =
=  [1-9][0-9][0-9][0-9]-
  ((0[1-9]|1[0-2])-([01][1-9]|10|2[0-8])
    |(0[13-9]|1[0-2])-(29|30)|(0[13578]|1[02])-31)
|([1-9][0-9](0[48]|[2468][048]|[13579][26])|(0[48]|[2468][048]|[13579][26])00)-02-29

Der entstandene reguläre Ausdruck sieht zwar einigermaßen verwirrend aus, kennt man aber seine Entstehungsgeschichte, so muss man zugeben, dass er eigentlich gar nicht so schwer zu konstruieren war. So etwas ist typisch für reguläre Ausdrücke: sie sehen meist erheblich komplizierter aus als sie sind.

Theorie

Ganz am Anfang war eine Theorie von „besonderer Schönheit“ versprochen worden. Über Schönheit lässt sich bekanntlich streiten, und die Schönheit mathematischer Theorien erschließt sich nicht jedem sofort, genauso wenig wie die Schönheit mancher anderen Kunstwerke. Mathematiker betrachten Theorien dann als besonders schön, wenn aus wenigen und einfachen Definitionen viele Aussagen hergeleitet werden können, die in einem inneren Zusammenhang stehen.

Was bisher geliefert wurde, entspricht sehr wenig diesem Bild. Das in der voranstehenden Einführung enthaltene Beispiel eines regulären Ausdrucks wirkt einerseits kryptisch und damit hässlich, andererseits in gewisser Weise zufällig: warum hat man sich gerade für diesen Satz von Notationen entschieden, mit dem man manche Sprachen darstellen kann, andere aber nicht? In diesem Kapitel wird sich herausstellen, dass es darauf nur in geringem Maße ankommt. Auch andere Sätze von Notationen hätten vielleicht zum selben Ergebnis geführt. Es gibt nämlich eine ganze Reihe von Eigenschaften, die die regulären, also die durch reguläre Ausdrücke definierbaren Sprachen haben und andere Sprachen eben nicht. Viele Notationen, die man hinzufügen könnte, würden am beschreibbaren Sprachumfang nichts ändern, und man könnte umgekehrt manches auch weglassen und damit zwar Einbußen bei der Bequemlichkeit der Notation hinnehmen, nicht aber bei dem, was überhaupt darstellbar ist.

Der Begriff der regulären Sprache lässt sich durchaus auch ganz anders definieren als dadurch, dass es eben die Sprachen sind, die sich mit einem Satz mehr oder weniger willkürlich ausgewählter Operatoren beschreiben lassen. In diesem Kapitel werden ganz verschiedene Begriffsbildungen vorgestellt, von denen sich dann herausstellen wird, dass sie in ganz verschiedener Weise dasselbe aussagen. In der Mathematik ist so eine Situation, nämlich dass sich mehrere sehr verschieden aussehende Begriffswelten als äquivalent erweisen, oft ein Indiz dafür, dass der zugrunde liegende Begriff ein wichtiger Grundbegriff der Theorie ist. So ist auch hier: die Menge der regulären Sprachen weist eine so hohe Anzahl von Gesetzmäßigkeiten auf wie kaum eine andere Klasse formaler Sprachen.

Die Lektüre dieses Kapitels dient hauptsächlich der Bildung und nicht so sehr der Ausbildung des Lesers. Für die meisten praktischen Anwendungen kommt man ohne diese Kenntnisse aus. Höchstens bei der Konstruktion sehr verzwickter regulärer Ausdrücke können sie von Nutzen sein, wie die anschließenden Beispiele belegen, besonders das erste.

Endliche Automaten

Wir stellen uns zunächst eine Frage, die mit regulären Ausdrücken nicht zu tun hat – oder wenigstens nicht zu tun zu haben scheint. Bei manchen Sprachen, zum Beispiel der deutschen, kann man sich beliebig tief in Nebensätze verschachteln, und man braucht ein unbegrenzt großes Gedächtnis, um sich für jeden angefangenen Satz merken zu können, wie er potenziell weitergeht. In der Praxis gibt es natürlich nur endlich viele Fortsetzungen: jeder Redner wird schon aufgrund seiner beschränkten Redegeschwindigkeit und ebenfalls beschränkten Lebenszeit Sätze nur beschränkt tief verschachteln können – sogar nur endlich viele verschiedene Sätze sagen können –, aber von der Sprache her könnte man unbeschränkt viele Satzanfänge konstruieren, die alle nach unterschiedlichen Vervollständigungen verlangen. Ein viel einfacheres Beispiel sind mathematische Formeln: es müssen rechts von einer beliebigen Stelle in der Formel so viele Klammern geschlossen werden, wie links davon geöffnet wurden, was eine unendliche Anzahl von Möglichkeiten bedeutet. Wohlgemerkt: es geht nicht nur darum, dass auf ein gegebenes Anfangsstück unendlich viele Enden möglich sind (das ist immer erreichbar, wenn die Sprache selbst unendlich viele Wörter enthält), sondern dass man unendlich viele Anfangsstücke präsentieren kann, die alle verschiedene Mengen von Ergänzungen zu korrekten Wörtern der Sprache haben. Mit dem nächsten Beispiel wird das hoffentlich viel klarer. Nun ergibt sich die Frage, ob es nicht besonders einfache Sprachen gibt, bei denen das nicht vorkommt.

Endliche Sprachen, also Sprachen mit endlich vielen Wörtern, haben offensichtlich diese Eigenschaft. Aber auch die Sprache aus dem Beispiel in der Einführung gehört dazu, obwohl sie unendlich ist. An jeder Stelle des Lesens ist man nämlich entweder:

  1. ganz am Anfang
  2. hinter einem einleitenden Vorzeichen: als restlicher Text darf nur noch eine vorzeichenlose Zahl kommen
  3. nach mindestens einer Ziffer: die Zahl darf hier schon zu Ende sein oder es darf nur noch eine vorzeichenlose Zahl kommen, die aber (weil schon eine Ziffer gelesen wurde) auch gleich mit dem Komma beginnen darf
  4. nach dem Komma: jetzt dürfen nur noch Ziffern (und zwar mindestens eine) kommen
  5. nach Komma und mindestens einer Ziffer: die Zahl darf hier zu Ende sein oder es kommen nur noch Ziffern

Es gibt also nur fünf, also endlich viele, verschiedene Möglichkeiten, wo man sein kann, im Gegensatz zu Sprachen mit Klammerstruktur, wo es unendlich viele Möglichkeiten gibt.

Dieser Sachverhalt lässt sich auch grafisch darstellen. Die fünf Stellen, wo man sich befindet, sind hier durch Kreise dargestellt, und die Pfeile deuten an, wie man durch Weiterlesen des nächsten Zeichens (das Pluszeichen steht hier abkürzend für ein beliebiges Vorzeichen und die Ziffer 1 für eine beliebige Ziffer) von einem dieser Zustände in einen anderen gelangt. Der hineingehende Pfeil beim Zustand A deutet an, dass es dort losgeht, und der herausgehende bei den Zuständen C und E sagt aus, dass dort der zu analysierende String zu Ende sein darf. Auf welchem Wege man auch immer beim hineingehenden Pfeil das Schema betritt, dort entlang der Pfeile weitergeht und es bei einem der beiden herausgehenden Pfeile verlässt: immer bilden die Beschriftungen der Pfeile hintereinander gelesen ein zulässiges Wort der Sprache. Umgekehrt gibt es auch zu jedem zulässigen String einen solchen Weg durch das Schema.

Man versuche einmal, ein solches Schema für die Sprache zu zeichnen, deren Wörter nur aus öffnenden und danach ebenso vielen schließenden Klammern bestehen, die also die Wörter (), (()), ((())), … und nur diese enthält. Es wird nicht gelingen: entweder akzeptiert das Schema nicht alle diese Wörter oder darüber hinaus welche, bei denen die Zahl der schließenden Klammern nicht mit der der öffnenden übereinstimmt.

Ein solches Schema heißt deterministischer endlicher Automat. Man stellt sich also eine Art Maschine vor, die anfangs im Anfangszustand (dem mit dem hineingehenden Pfeil) ist, dann beim Lesen jeweils eines Zeichens des Textes von einem Zustand in einen anderen (oder auch wieder in denselben) übergeht und beim Erreichen des Textendes „akzeptiert“ verkündet, wenn sie sich dann in einem der Endzustände (also einem mit einem herausgehenden Pfeil) befindet. In den übrigen Fällen, nämlich entweder dem Erreichen eines Nicht-Endzustandes am Textende oder dem Erreichen eines Zustandes unterwegs, bei dem es mit dem nächsten Zeichen nicht weitergeht, wird der String nicht akzeptiert. Endlich heißt der Automat, weil er nur endlich viele Zustände hat, und deterministisch, weil der Weg durch den String eindeutig festgelegt ist: es gibt nur einen Anfangszustand und zu jedem Zustand und jedem Zeichen höchstens einen Pfeil, der mit diesem Zeichen aus diesem Zustand in den nächsten führt.

Hier ist noch ein ganz anderes Beispiel für einen deterministischen endlichen Automaten: dieser Automat akzeptiert die durch drei teilbaren natürlichen Zahlen in Dezimalschreibweise, wobei der leere String auch akzeptiert wird. Dabei steht die Ziffer 0 (als Beschriftung eines Zustandsübergangs) abkürzend für eine der Ziffern 0, 3, 6 oder 9, die 1 für eine der Ziffern 1, 4 oder 7 und die 2 für eine der Ziffern 2, 5 oder 8. Die Idee ist ganz einfach: Im Zustand, der mit 0 bezeichnet ist, ist bisher noch gar nichts oder eine durch drei teilbare Zahl gelesen worden, und im Zustand 1 (oder 2) eine Zahl, die bei Division durch 3 den Rest 1 (bzw. 2) lässt. Jetzt muss man nur noch die Übergänge verifizieren. Beispielsweise besagt der mit 2 beschriftete Übergang vom Zustand 2 in den Zustand 1 (unten in der Mitte der Zeichnung), dass man beim Anhängen einer 2, 5 oder 8 an eine Zahl, die bei Division durch 3 den Rest 2 lässt, eine mit dem Rest 1 erhält, wie man unschwer nachrechnet. Dass das funktioniert, hat übrigens nichts mit der Dreierprobe aus der Grundschule zu tun: es geht ganz genauso für jeden beliebigen Divisor; nur wäre die Zeichnung schon für den Divisor 7 oder 13 mit 7 bzw. 13 Zuständen und 49 bzw. 130 Übergängen reichlich unübersichtlich geworden.

Ein deterministischer endlicher Automat lässt sich unmittelbar in ein Programm umschreiben, bei dem jeder Zustand als Marke und jeder Übergang als Sprung auf eine solche Marke dargestellt wird. Im allgemeinen gilt zwar das Programmieren mittels der GOTO-Anweisung als nicht gerade übersichtlicher Programmierstil; hier wollen wir aber einmal eine Ausnahme machen. Wir müssen natürlich eine Programmiersprache verwenden, in der, anders als etwa in Java, GOTO eine zulässige Anweisung ist. Aus Nostalgiegründen nehmen wir für das Beispiel die Sprache FORTRAN77 her; in anderen Sprachen sieht es auch nicht viel anders aus:

      subroutine drei (x)
      character*(*) x
      integer i, l
      character c
      logical rest0, rest1, rest2
      rest0(c) = c.eq.'0' .or. c.eq.'3' .or. c.eq.'6' .or. c.eq.'9'
      rest1(c) = c.eq.'1' .or. c.eq.'4' .or. c.eq.'7'
      rest2(c) = c.eq.'2' .or. c.eq.'5' .or. c.eq.'8'
      i = 0
      l = len (x)

C     Zustand 0
 1000 i = i+1
      if (i .gt. l) goto 9001
      if (rest0(x(i:i))) goto 1000
      if (rest1(x(i:i))) goto 1001
      if (rest2(x(i:i))) goto 1002
      goto 9000

C     Zustand 1
 1001 i = i+1
      if (i .gt. l) goto 9000
      if (rest0(x(i:i))) goto 1001
      if (rest1(x(i:i))) goto 1002
      if (rest2(x(i:i))) goto 1000
      goto 9000

C     Zustand 2
 1002 i = i+1
      if (i .gt. l) goto 9000
      if (rest0(x(i:i))) goto 1002
      if (rest1(x(i:i))) goto 1000
      if (rest2(x(i:i))) goto 1001
      goto 9000

C     String ablehnen
 9000 print *, '"', x, '" ist falsch.'
      return

C     String akzeptieren
 9001 print *, '"', x, '" ist richtig.'
      return
      end

      program probier
      call drei ('')
      call drei ('5317')
      call drei ('3')
      call drei ('2288962946180602796295895129457306782916305881')
      call drei ('2288962946180602796295895129457306782916305882')
      end

Gegenüber einer schlichten Probedivision hat das Programm den Vorteil, dass es beliebig lange Dezimalzahlen als Eingabe akzeptiert. Die für uns interessanteste Eigenschaft dieses Programms ist aber eine andere: der Speicherbedarf steht von vorneherein fest. Es werden keine Variablen dynamisch alloziert, es werden keine Unterprogramme rekursiv aufgerufen; kurz, der Speicherbedarf für die Variablen ist genau durch die statisch niedergeschriebenen Variablendeklarationen gegeben. Ein Rechner mit diesem Programm ist also wirklich ein „deterministischer endlicher Automat“. Man könnte auch umgekehrt die Eigenschaft einer Sprache, durch ein Programm mit vorher fixiertem Speicherbedarf analysierbar zu sein, anstelle endlicher Automaten zur Definition verwenden, muss dann aber sehr aufpassen, den Speicherbedarf richtig zu definieren. Wir verfolgen diesen Weg hier nicht weiter.

Vervollständigung und Komplementierung endlicher Automaten

Bei der Einführung endlicher Automaten gab es zwei Gründe, aus denen ein endlicher Automat einen vorgelegten Text nicht akzeptiert: entweder weil er sich am Textende in einem Zustand befindet, der kein Endzustand ist, oder weil in einem Zustand unterwegs das anstehende Zeichen nicht unter denen ist, für die es einen Folgezustand gibt. Wir sehen uns dazu noch einmal den Automaten aus den ersten Beispiel an: hier würde man mit dem String 1, im Zustand D landen, der kein Endzustand ist, und mit dem String 1+ in überhaupt keinem Zustand. Der zweite Fall ist ein sicheres Indiz dafür, dass der String auch nicht zu einem korrekten Wort fortgesetzt werden kann. Man kann nun den endlichen Automaten durch einen zusätzlichen Zustand zu einem Automaten ergänzen, bei dem der zweite Fall nie eintritt: der nebenstehende Automat geht immer dann in den Zustand F über, wenn der ursprüngliche nicht mehr weitergewusst hätte. Mit dieser Art von Vervollständigung vereinfacht sich die Beschreibung der Funktionsweise des Automaten: jetzt gibt es immer Zustandsübergänge, egal, wo man ist und was kommt, und es kommt für die Akzeptanz eines Strings nur noch auf den erreichten Zustand am Textende an. Der Preis, den man dafür bezahlt, ist dass man sich jetzt auf ein bestimmtes Alphabet festgelegt hat, während vorher das Alphabet einfach implizit als die Menge der bei den Zustandsübergängen vorkommenden Zeichen gegeben war.

Bei der wichtigsten Anwendung vollständiger endlicher Automaten muss man sich ohnehin auf ein bestimmtes Alphabet festlegen, nämlich bei der Konstruktion von Automaten, die genau die Strings akzeptieren, die nicht in einer vorgegebenen Menge liegen. Will man etwa einen Automaten konstruieren, der genau die Strings akzeptiert, die keine Zahlen im Sinne des ersten Beispiels sind, so muss man trotzdem sagen, über welchem Alphabet diese Strings gebildet werden, weil sonst die Forderung nach endlichen Alphabeten verletzt wäre. Der nebenstehende Automat akzeptiert etwa genau die Strings über dem Alphabet aus Ziffern, Vorzeichen und Komma, die der vorangegangene Automat gerade nicht akzeptiert. Hier wird von dessen Vollständigkeit Gebrauch gemacht, indem einfach nur die Zustände zu Endzuständen ernannt werden, die vorher keine waren und umgekehrt. Auf den zusätzlichen Zustand F kann man jetzt nicht mehr verzichten.

Kombination mehrerer endlicher Automaten zu einem einzigen

Wir beginnen mit einem Beispiel. Bekanntlich ist ja die anglo-amerikanische Schreibweise von Datumsangaben nicht immer besonders eindeutig: der 01/02/03 könnte der 2. Januar oder der 1. Februar des Jahres 03 sein oder vielleicht auch der 3. Februar 01. Manchmal lässt sich mehr sagen, wenn etwa ein Tagesdatum jenseits der 12 liegt oder eine Jahreszahl vierstellig geschrieben ist. Wir werden jetzt versuchen, mit Hilfe endlicher Automaten die verschiedenen Möglichkeiten zu beschreiben.

Dazu nehmen wir an, dass ein Programm die Datumsangabe schon in ihre Bestandteile gegliedert und dabei festgestellt hat, was jede der Ziffernfolgen möglicherweise bedeuten kann. Dabei ist die Einteilung so gewählt, dass jede Ziffernfolge eindeutig in eine der folgenden Klassen gehört, dass aber die meisten Klassen mehrdeutig sind hinsichtlich der Entscheidung, ob es sich um eine Tages-, Monats- oder Jahresangabe handelt. Die Klassen sind:

Klasse Ziffernfolge Bedeutung
m 2-stellige Zahl von 01 bis 12 Tag, Monat oder Jahr
t 2-stellige Zahl von 13 bis 31 Tag oder Jahr
j andere 2-stellige Zahl oder 4-stellige Zahl Jahr
e 1-stellige Zahl von 1 bis 9 Tag oder Monat

Als erstes bauen wir je einen endlichen Automaten für die drei Interpretationsmögichkeiten:

Der erste akzeptiert Datumsangaben der Form Tag/Monat/Jahr. Weil das die britische Variante ist, soll sein Endzustand B heißen. Die Tagesangabe ist nach obiger Tabelle ein String nach einem der Muster e, m oder t; deswegen ist der erste Übergang mit emt bezeichnet (das bedeutet also hier nicht den String emt!). Der dritte Übergang trägt entsprechend die Beschriftung em, weil Monate mit Strings bezeichnet werden, die entweder dem Muster e oder dem Muster m nach der Tabelle genügen. Schließlich ist der fünfte Übergang mit mtj bezeichnet, nach den drei Alternativen, eine Jahreszahl zu schreiben.

Der zweite Automat akzeptiert Datumsangaben der amerikanischen Form Monat/Tag/Jahr; dementsprechend sind die Beschriftungen des ersten und dritten Übergangs gegenüber dem voranstehenden Automaten vertauscht. Die Bezeichnungen der Zustände, die ja für die akzeptierte Sprache keine Rolle spielen, sind so gewählt worden, dass es keine Überschneidungen zwischen den beiden Automaten gibt. Schließlich gibt es noch einen dritten Automaten für Datumsangaben der Form Jahr/Monat/Tag. Hier sind die Beschriftungen der Übergänge gerade die vom ersten Automaten in umgekehrter Reihenfolge.

Jetzt wollen wir die in diesen drei Automaten insgesamt vorhandene Information durch einen einzigen Automaten darstellen. Die Zustände des neuen Automaten sind jeweils Kombinationen von Zuständen der drei alten und geben an, in welchen Zustand man sich befinden könnte, je nachdem, mit welchem der Anfangszustände man gestartet ist. Der Anfangszustand ist also CHM, da man ja nicht wissen kann, welcher der drei Anfangszustände C, H und M gegolten hat. Kommt in diesem Zustand ein m, so ist damit kein Stück mehr Klarheit geschaffen, und man ist im Zustand DIN. Kommt hingegen ein j, so kann das überhaupt nur der Fall sein, wenn man sich im Zustand M des dritten Automaten befunden hat, und der Folgezustand ist eindeutig N. Mit den beiden anderen Eingabezeichen kann man jeweils einen der drei denkbaren Folgezustände ausschließen und erhält so die Zustände DI und DN, die nur noch jeweils zwei Interpretationen im Sinne der drei alten Automaten zulassen.

Der kombinierte Automat landet mit einem String genau dann in einem der Endzustände, der B (oder A oder Y) in seinem Namen hat, wenn der erste (bzw. zweite bzw. dritte) der einzelnen Automaten mit diesem String in seinem Endzustand B (bzw. A bzw. Y) gelandet wäre. Insofern erfüllt er wirklich die Aufgabe aller drei Automaten gleichzeitig.

Trotzdem sieht jetzt alles viel komplexer aus als zu der Zeit, als es noch drei getrennte Automaten waren. Was ist also damit gewonnen? Vier Dinge:

Nichtdeterministische endliche Automaten

Wie bei der Einführung der deterministischen Automaten schon erwähnt, ergibt sich die einfache Prüfung eines Strings auf Zugehörigkeit zu der vom Automaten akzeptierten Sprache daraus, dass es an genau einer Stelle losgeht und dann mit jedem Zeichen an höchstens einer Stelle weitergeht. Was würde geschehen, wenn man diese Einschränkung fallen lässt, indem man erlaubt

Für diesen jetzt nichtdeterministischen endlichen Automaten wird definiert, dass er einen String dann akzeptiert, wenn es wenigstens einen Weg von einem der Anfangszustände zu einem der Endzustände gibt, bei dem die Beschriftungen der Übergänge hintereinander gelesen den String ergeben.

Ohne es zu bemerken, haben wir im vorigen Abschnitt schon einen nichtdeterministischen endlichen Automaten kennengelernt: die drei einzelnen Automaten für die drei Datumsnotationen bilden zusammen einen nichtdeterministischen Automaten mit drei Anfangszuständen, der alle Datumsnotationen akzeptiert. Der darunter stehende kombinierte Automat akzeptiert genau dieselbe Sprache. Die Art und Weise , wie hier aus einem nichtdeterministischen ein deterministischer endlicher Automat für dieselbe Sprache gemacht wurde, lässt sich ganz genauso auf jeden nichtdeterministischen Automaten anwenden. Von der Tatsache, dass die drei Automaten nicht nur getrennt gestartet haben, sondern stets getrennt geblieben sind, haben wir nämlich an keiner Stelle Gebrauch gemacht. Wir ersparen uns, das im Detail vorzuführen; die Methode ist wirklich genau dieselbe wie bei der Kombination mehrerer endlicher Automaten zu einem einzigen.

Um zu einer gegebenen Sprache einen deterministischen endlichen Automaten anzugeben, genügt es also, einen nichtdeterministischen zu finden und diesen dann mit dem geschilderten Verfahren nachträglich deterministisch zu machen. Darin liegt auch die Hauptbedeutung nichtdeterministischer endlicher Automaten.

Minimierung endlicher Automaten

(wird später geschrieben)

Reguläre Ausdrücke

Das Beispiel aus der Einleitung legt nahe, dass reguläre Ausdrücke eine gewisse Ähnlichkeit mit algebraischen Ausdrücken haben, wie wir sie aus der Schule kennen. Es gibt darin ganz genauso Operatoren, nur eben andere: es gibt kein Malzeichen für die Multiplikation, weil man Sprachen nicht multiplizieren kann, dafür gibt es andere Operatoren, die eben auf Sprachen sinnvoll angewendet werden können. Die Operanden dieser Operatoren sind dementsprechend keine Zahlen und auch keine Ausdrücke mit einem Zahlenwert, sondern Sprachen und Ausdrücke, die Sprachen beschreiben. Daran, dass Ausdrücke eben nichts mit Zahlen zu tun haben, muss man sich vielleicht ein wenig gewöhnen. Es gibt aber überhaupt keinen Grund anzunehmen, dass es sich bei Dingen, die mit algebraischen Ausdrucken beschrieben werden, immer um so etwas wie Zahlen handeln muss.

Auch aus der Mengenlehre kennt man ja Ausdrücke, die keine Zahlen, sondern Mengen darstellen. Da Sprachen auch Mengen sind, nämlich Mengen von Wörtern, wird man die Mengenoperationen wie Vereinigung, Durchschnitt und Mengendifferenz unter den Operationen finden, die auf Sprachen operieren. Aber diese reichen nicht aus, um Aussagen über die Gestalt der Wörter einer Sprache zu machen. Dazu müssen wir weitere Operatoren einführen.

Die wichtigste ist dabei die folgende: Unter der Konkatenation zweier Wörter versteht man das Wort, das durch Hintereinanderschreiben aus den beiden Wörtern entsteht, z.B. ist die Konkatenation der Wörter reg und ulär das Wort regulär. Die Konkatenation von mehreren Wörtern ist entsprechend definiert – es kommt ja nur auf die Reihenfolge der Bestandteile an, nicht aber auf die Reihenfolge der Konkatenationsvorgänge. Hier sieht man wieder, dass wir hier nur Syntax und keine Semantik betreiben: werden etwa die Wörter mädchen, handels, schule konkateniert, so lautet das Ergebnis mädchenhandelsschule, unabhängig davon, welche Zusammensetzung zuerst durchgeführt wurde; für die Semantik könnte das schon von Belang sein. Schließlich bemerken wir noch, dass die Konkatenation von null Wörtern das leere Wort ergibt.

Das war jetzt eine Operation auf Wörtern und nicht eine Operation auf Sprachen. Sie lässt sich aber unmittelbar auf ganze Sprachen übertragen (siehe Punkt 3 unten).

Ganz am Anfang dieses Artikels war eine nicht-mathematische Behandlung versprochen worden, ohne formale Definitionen, Sätze und Beweise. Mit der folgenden Definition des Begriffs regulärer Ausdruck, der ja bisher nur in Form eines Beispiels vorkam, wollen wir einmal eine Ausnahme machen. Zum einen mag es ganz interessant sein, zu sehen, wie man so etwas präzis definiert, zum zweiten ist ein gewisses Maß an Präzision notwendig, um Operationen auf Sprachen nicht mit Operationen auf Wörtern zu verwechseln, wie das eben schon beinahe geschehen wäre, zum dritten schließlich kann diese Definition auch gleichzeitig als Beispiel für eine Definition einer nicht-regulären Sprache dienen, wie sie für spätere Erläuterungen (die noch nicht geschrieben sind) gebraucht wird.

Es handelt sich um eine rekursive Definition. Das bedeutet, dass der zu definierende Begriff selbst in der Definition verwendet wird. Eine solche rekursive Definition erhält immer Teile, bei denen das nicht vorkommt (hier die Punkte 1 und 2), aus denen dann die anderen aufgebaut werden. Das Beispiel nach der Definition wird das erläutern.

  1. ∅ ist ein regulärer Ausdruck, der die leere Sprache beschreibt, d.h. die Sprache, die kein Wort enthält, nicht einmal das leere.

  2. Für jedes Zeichen a ist a ein regulärer Ausdruck, der die Sprache beschreibt, die genau ein Wort enthält, wobei dieses Wort genau aus dem Zeichen a besteht.

  3. Sind E1 und E2 reguläre Ausdrücke, die die Sprachen L1 und L2 beschreiben, so ist (E1)(E2) ein regulärer Ausdruck, der die Sprache beschreibt, deren Wörter jeweils aus einem Wort aus L1 und einem Wort aus L2 konkateniert sind.

  4. Ist E ein regulärer Ausdruck, der die Sprache L beschreibt, so ist (E)* ein regulärer Ausdruck, der die Sprache beschreibt, deren Wörter sich als endliche (auch leere) Konkatenationen von Wörtern aus L schreiben lassen. Diese Sprache heißt auch der Kleene’sche Abschluss von L nach Stephen Cole Kleene (1909-1994); Aussprache: [ˈkleɪni].

  5. Sind E1 und E2 reguläre Ausdrücke, die die Sprachen L1 und L2 beschreiben, so ist (E1)|(E2) ein regulärer Ausdruck, der die Sprache beschreibt, deren Wörter in L1 oder in L2 vorkommen, also die Vereinigungsmenge der beiden Sprachen.

  6. Sind E1 und E2 reguläre Ausdrücke, die die Sprachen L1 und L2 beschreiben, so ist (E1)&(E2) ein regulärer Ausdruck, der die Sprache beschreibt, deren Wörter in L1 und in L2 vorkommen, also den Durchschnitt der beiden Sprachen.

  7. Sind E1 und E2 reguläre Ausdrücke, die die Sprachen L1 und L2 beschreiben, so ist (E1)\(E2) ein regulärer Ausdruck, der die Sprache beschreibt, deren Wörter in L1, aber nicht in L2 vorkommen, also die Differenzmenge der beiden Sprachen.

Die Klammern dürfen weggelassen werden, wenn trotzdem Eindeutigkeit besteht, zum Beispiel bei der Konkatenation oder Vereinigung von mehr als zwei Sprachen nach Regel 3 bzw. 5. Außerdem bindet der Stern für den Kleene’schen Abschluss stärker als die anderen Operatoren und das Hintereinanderschreiben für die Konkatenation stärker als die explizit hingeschriebenen zweistelligen Operatoren. Das Zeichen \ klammert nach links: K\L\M bedeutet also (K\L)\M. Man kann diese Klammerungs- und Vorrangregeln auch direkt in die Definition aufnehmen, was aber zur leichten Verständlichkeit nicht unbedingt beiträgt; dafür lassen sich aus so geschriebenen Definitionen leichter auf automatischem Weg Programme generieren, die Ausdrücke in ihre Bestandteile zerlegen.

Als Beispiel wollen wir die Sprache aus dem Beispiel in der Einleitung mit einem so definierten regulären Ausdruck beschreiben. Dabei gehen wir schrittweise vor:

Wie man sieht, stört es kein bisschen, dass die Definition den zu definierenden Begriff selbst enthält, schließlich wird ja ein regulärer Ausdruck höchstens unter Berufung auf einen bereits gebildeten anderen, nie aber auf sich selbst konstruiert. Manchmal wird übrigens bei einer rekursiven Definition explizit dazugeschrieben, dass nur das damit definiert ist, was sich durch endlich viele Anwendungen der Regeln bilden lässt; aber auch wenn es wie hier nicht dabeisteht, ist es immer so gemeint.

Der reguläre Ausdruck ist viel länger geworden als in der Einleitung. In der praktischen Anwendung bevorzugt man nämlich abkürzende, übersichtliche Notierungen, während in der Theorie möglichst wenige verschiedene Operatoren eingesetzt werden, um die Herleitung von Sätzen einfacher zu gestalten.

Diesem Ziel dient auch die folgende Festlegung: Wir nennen den regulären Ausdruck einfach, wenn er die Operatoren Durchschnitt und Mengendifferenz nicht enthält; ein verallgemeinerter regulärer Ausdruck ist einer, der diese beiden Operatoren auch enthalten darf. Es wird sich herausstellen, dass man mit verallgemeinerten regulären Ausdrücken keine Sprachen beschreiben kann, die man nicht auch mit einfachen regulären Ausdrücken beschreiben kann. Die mit regulären Ausdrücken beschreibbaren Sprachen heißen reguläre Sprachen. Das sind gerade diejenigen Sprachen, die von deterministischen endlichen Automaten akzeptiert werden, womit der Zusammenhang des vorangegangenen Abschnittes zum Thema des gesamten Artikels endlich hergestellt wäre.

Die hier eben aufgestellten Behauptungen bilden einen der Kernpunkte der Theorie und werden deshalb hier noch einmal in fetter Schrift wiederholt und, wenn schon nicht bewiesen, so doch wenigstens plausibel gemacht:

Diese Zusammenstellung legt nahe, dass der Weg, aus einem verallgemeinerten regulären Ausdruck einen einfachen zu erhalten, über den endlichen Automaten führt. So sehr das wie ein Umweg aussieht, ist es doch tatsächlich oft einer der kürzesten Wege zum Ziel.

Reguläre Ausdrücke für endliche Automaten

Der endliche Automat, der als unser erstes Beispiel diente, lässt sich ziemlich einfach in einen regulären Ausdruck umschreiben. Drei wiederholt einsetzbare Schritte reichen dafür aus, bei denen der Automat jeweils vereinfacht wird, wobei allerdings die Übergänge mit regulären Ausdrücken statt mit einzelnen Zeichen versehen werden:

  1. Hat ein Zustand die Eigenschaft, dass nur ein Übergang von außen hineingeht und ein Übergang nach außen herausführt, so wird der Zustand mit seinen beiden Übergängen durch einen neuen Übergang ersetzt, der mit der Konkatenation der Ausdrücke auf den alten Übergängen markiert wird.

  2. Hat ein Zustand eben diese Eigenschaft, aber zusätzlich eine Schlinge, also einen Übergang auf sich selbst, so wird der Zustand mitsamt seiner Schlinge und seinen beiden äußeren Übergängen durch einen neuen Übergang ersetzt, der mit der Konkatenation der Ausdrücke auf den äußeren Übergängen markiert wird, zwischen die der Kleene’sche Abschluss des Ausdrucks auf der Schlinge eingefügt wird.

  3. Gibt es zwei parallele Übergänge, so werden sie durch einen einzigen mit der Vereinigung der Sprachen auf den Übergängen ersetzt.

Man ersetzt also den Zustand B mit seinen Übergängen nach Regel 1 durch einen Übergang von A nach C mit +1, ebenso den Zustand D mit seinen Übergängen durch einen Übergang von C nach E mit ,1. Nach Regel 3 können die beiden parallelen Übergänge von A nach C durch einen einzigen mit +1|1 ersetzt werden. Nach der ersten Ersetzung erfüllt der Zustand E die Voraussetzung für Regel 2, wenn man die Außenwelt, in die der Pfeil ganz rechts führt, wie einen Zustand behandelt: Man kann den Weg von C über E nach außen durch einen Übergang direkt von C nach außen ersetzen, der mit ,11* bezeichnet ist. Es bleibt dem Leser überlassen, dieses Beispiel zu Ende zu führen, indem auch noch die restlichen Zustände eliminiert werden.

Für viele in der Praxis vorkommenden Anwendungen regulärer Ausdrücke reichen diese Regeln aus, leider aber nicht für den allgemeinen Fall. Ihre Anwendung setzt nämlich voraus, dass die Zyklen, also die Wege, die von einem Zustand nach einem oder mehreren Schritten wieder in denselben Zustand führen, sich auf einfache Wege reduzieren lassen. Im Beispiel links ist das nicht der Fall: keiner der Zustände lässt sich hier mit den obigen Regeln eliminieren.

In so einem Fall splittet man einen Zustand auf; wir nehmen hier beispielsweise den Zustand C, den wir in C0 und C1 splitten. Einer der beiden neuen Zustände erhält alle hineingehenden Übergänge und wird Endzustand, hier C1, der andere alle herausgehenden Übergänge und wird Anfangszustand, hier C0. Das Ganze ist jetzt nicht als nichtdeterministischer Automat zu lesen, wie es die Zeichnung eigentlich nahelegt, sondern nur als gemeinsame Zeichnung für vier verschiedene deterministische endliche Automaten:

Die Gesamtheit der Wege von A nach E im ursprünglichen Automaten besteht offenbar aus allen Wegen, die überhaupt nicht bei C vorbeikommen, sowie aus allen Wegen, die von A direkt (d.h. nicht über C) nach C führen, danach beliebig oft direkt von C nach C und schließlich direkt von C nach E. Damit sieht man unmittelbar die Sprache aba|(abc|b)(abc)*(aba|c).

In komplizierten Fällen wird man mehr als einmal einen Zustand splitten müssen. Man kann aber leicht zeigen, dass die resultierenden deterministischen endlichen Automaten zwar immer zahlreicher, aber auch jeweils immer einfacher werden, so dass das Verfahren terminiert.

Beispiele

Mehrfach maskierter Text (zweiter Versuch)

Wir wenden uns noch einmal der Aufgabe zu, einen regulären Ausdruck für alle jene Unix-Kommandozeilen zu konstruieren, bei denen alle mit Apostroph oder Anführungszeichen begonnenen Texte ordnungsgemäß abgeschlossen sind. Die Spezifikation entnehmen wir der ersten Beschreibung dieser Aufgabe. Jetzt erstellen wir die dort angekündigte Übersicht über „alle Möglichkeiten, wie die verschiedenen Maskierungszeichen aufeinander einwirken“:

Situation Beurteilung des Textes
bei Textende in dieser Situation		 Situation nach
['] ["] [\] [^'"\]
U unmaskierter Text Text in Ordnung A Q B U
A in Apostrophen schließender Apostroph fehlt U A A A
B nach Backslash außen Text endet mit Backslash als Maskierungszeichen U U U U
Q in Anführungszeichen schließendes Anführungszeichen fehlt Q U R Q
R nach Backslash in Anführungszeichen schließendes Anführungszeichen fehlt Q Q Q Q

Diese Tabelle liest sich so: anfangs befinden wir uns im unmaskierten Text, also an einer Stelle, an der alle Apostrophe und Anführungszeichen noch nicht geöffnet oder aber schon wieder wieder geschlossen sind; diesen Fall kürzen wir mit U ab. Kommt dann eines der drei Maskierungszeichen, so verändert sich auf jeden Fall die Situation; die drei neuen Situationen kürzen wir mit A (für Apostroph), B (für Backslash) und Q (für Anführungszeichen, engl. quote) ab. Die folgenden drei Tabellenzeilen machen dann Aussagen über die jeweils dort entstandene Situation. Man mache sich die übrigen Tabellenzeilen ebenso klar.

Wenn man eine solche Tabelle anlegt, stellt man auf jeden Fall sicher, dass man keine möglicherweise auftretende Situation vergisst. Im Zweifelsfall ist es besser, mehr verschiedene Situationen zu unterscheiden; man kann sie ja nachträglich noch zusammenfassen, wenn sich herausstellt, dass in ihnen jeweils dieselben nächsten Zeichen dieselben Reaktionen auslösen.

Diese Tabelle können wir natürlich auch grafisch darstellen, und mit unserem mittlerweise erworbenen Wissen über endliche Automaten erkennen wir, dass eine Tabelle wie diese nur eine alternative Schreibweise für einen endlichen Automaten darstellt. Die Umwandlung eines endlichen Automaten in einen regulären Ausdruck ist für uns inzwischen eine leichte Standardaufgabe: in diesem einfachen Fall genügt sogar das vereinfachte Verfahren, das im Abschnitt über diese Umwandlung zuerst dargestellt wurde. In wenigen Schritten sind wir bei einem regulären Ausdruck:

Der letzte Ausdruck ist dann, wie man sieht (da U einziger Anfangs- und Endzustand ist), gleich der gesuchte reguläre Ausdruck. Nicht alle Maskierungen mit eckigen Klammern sind notwendig; es ist aber sicherer, sie bei solchen Zeichen, die wie diese in verschiedenen Umgebungen (Shells, Programmiersprachen) zur Maskierung verwendet werden, immer dazuzufügen.

Durch drei teilbare Dezimalzahlen

Wir haben eingangs durch Konstruktion eines endlichen Automaten gezeigt, dass die durch drei teilbaren Dezimalzahlen eine reguläre Sprache bilden. Jetzt wollen wir den dazugehörigen regulären Ausdruck angeben. Wir beginnen dabei zunächst mit der schon dort durchgeführten Vereinfachung, die Ziffern 0, 1 und 2 stellvertretend für alle Dezimalziffern zu betrachten und den leeren String auch zuzulassen; beide Vereinfachungen lassen wir erst am Schluss der Konstruktion wegfallen.

Das ist zunächst der endliche Automat, den wir schon betrachtet haben; die von ihm akzeptierte Sprache heiße L. Er ist zu eng vermascht, als dass wir mit dem vereinfachten Verfahren aus dem Abschnitt über die Konstruktion regulärer Ausdrücke aus endlichen Automaten etwas anfangen könnten. Also müssen wir zunächst einen Zustand splitten; wir wählen Zustand 0. Das ist sehr naheliegend, weil das der Anfangs- und Endzustand ist, so dass die Wege aus dem Anfangs- in den gesplitteten und die aus dem gesplitteten in den Endzustand einfach wegfallen.
Hier haben wir den Zustand 0 in zwei Zustände gesplittet: in einen, 0i, für die herausgehenden und einen anderen, 0f, für die hineingehenden Übergänge. Ist L1 die Sprache, die vom nebenstehenden Automaten akzeptiert wird, so ist L=L1*. Dieser Automat sieht nicht sehr ähnlich zum voranstehenden aus, weil er zur besseren Übersichtlichkeit auseinandergezogen wurde und daher die beiden Teile des alten Zustands 0 nicht mehr beieinander liegen. Es kommt aber nur auf die Übergänge an, und man verifiziert leicht, dass es noch dieselben sind wie vorher.
Weil auch der Automat vom letzten Schritt noch keine unmittelbare Darstellung als regulärer Ausdruck zulässt, muss abermals ein Zustand in derselben Weise gesplittet werden. Diesmal wählen wir den Zustand 2, den wir in 2i und 2f splitten. Sei nun L2 die Sprache, die auf dem Weg von 0i nach 0f akzeptiert wird, L3 die von 0i nach 2f, L4 die von 2i nach 0f und L5 die von 2i nach 2f. Dann ist, wie oben erläutert, L1=L2|L3L5*L4.
Das ist der Teil des Automaten, der für die Sprache L2 relevant ist; die übrigen Zustände werden auf dem Weg von 0i nach 0f ohnehin nicht erreicht. Man sieht unmittelbar, dass L2=0|10*2.
Analog der Teil des Automaten für die Sprache L4. Es ist also L4=1|20*2.
Schließlich dasselbe für L3=2|10*1. Für L5 sparen wir uns die Extrazeichnung, weil schon im Ausgangsbild alles so schön nah beieinander liegt, dass man sieht L5=0|20*1.

Jetzt muss man nur noch alle Formeln ineinander einsetzen und gewinnt so einen regulären Ausdruck für L:

L = L1* =
    = (L2|L3L5*L4)* =
    = (0|10*2|(2|10*1)(0|20*1)*(1|20*2))*

Schließlich lassen wir die beiden Vereinfachungen vom Anfang weg. Das Zeichen (nicht der Zustand!) 0 beim Automaten stand für eine der Ziffern 0, 3, 6 oder 9, also müssen wir die 0 im regulären Ausdruck durch [0369] ersetzen und analog die 1 durch [147] und die 2 durch [258]. Den leeren String schließen wir aus, indem ganz außen der Stern durch ein Pluszeichen ersetzt wird. Somit lautet der fertige reguläre Ausdruck für die durch drei teilbaren Dezimalzahlen:

([0369]|[147][0369]*[258]|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))+

Durch dreizehn teilbare Dezimalzahlen

Hier ist dasselbe Beispiel für einen größeren Teiler, nämlich 13, um zu demonstrieren, dass das Funktionieren der Konstruktion nicht davon abhängt, dass es eine einfache „Probe“, etwa eine Quersummenbildung, für die Teilbarkeit gibt.

Die erste Zeichnung stellt den gesamten endlichen Automaten dar, wobei im Inneren die Bezeichnungen der Zustandsübergänge weggelassen wurden, da man sie ohnehin nicht hätte lesen können. Man sieht eigentlich nur ein wildes Knäuel, in welchem von jedem Zustand aus zehn Übergänge für die möglichen zehn Ziffern ausgehen. Die zweite Zeichnung zeigt anhand aller von zwei willkürlich ausgewählten Zuständen ausgehenden Übergänge, wie sich die Gesamtheit der Übergänge aus dreizehn fächerartigen Bündeln von je zehn Übergängen zusammensetzt. In der zweiten Zeichnung kann man sich auch von der Richtigkeit der dargestellten Übergänge leicht überzeugen. Beispielsweise sagt der Bogen rechts außen aus: Hängt man an eine Zahl, die bei Division durch 13 den Rest 5 lässt, die Ziffer 5 an, so entsteht eine, die bei Division durch 13 den Rest 3 lässt. Ist nämlich die Zahl vorher 13k+5, so entsteht daraus 10·(13k+5)+5 = 130k+55 = 13·(10k+4)+3.

Die Konstruktion eines regulären Ausdrucks dazu überlassen wir gerne dem geneigten Leser – der muss dazu allerdings schon sehr geneigt sein.

Weder Fisch noch Fleisch

Warnung: Dies ist ein eher pathologisches Beispiel und wohl kaum zu irgend einer praktischen Anwendung geeignet. Es ist aber insofern lehrreich, als die Grenzen der Darstellbarkeit regulärer Sprachen durch die ERE-Notation ausgereizt werden.

Einen regulären Ausdruck anzugeben, mit dem der String Fisch und der String Fleisch und sonst nichts beschrieben wird, ist ganz einfach: entweder einfach Fisch|Fleisch oder, unter Berücksichtigung der Ähnlichkeit der beider Wörter, F(le)?isch. Wie aber konstruiert man einen regulären Ausdruck für „weder Fisch noch Fleisch“, also für alle Strings außer diesen beiden?

Mit regulären Ausdrücken kann man umgehen wie mit algebraischen Ausdrücken in der Mathematik: es sind algebraische Ausdrücke, deren Umformungsregeln im Theorie-Teil dieses Artikels stehen werden. Die Negation ¬ gehört zwar nicht zu den Operatoren, die in der ERE-Notation vorkommen können; das soll uns aber nicht hindern, sie für die Konstruktion eines regulären Ausdrucks bei den Zwischenschritten heranzuziehen.

Als erstes überlegen wir uns, wie die Negation eines einzelnen Strings, etwa des Strings sch, aussieht. Ist etwas nicht der String sch, so gibt es folgende Möglichkeiten:

In der Sprache der regulären Ausdrücke sieht das so aus:

¬(sch) = ([^s]|s[^c]|sc[^h]|sch.).*|(sc?)?

Analog dazu, aber unter Verwendung des Obigen:

¬(eisch) = ([^e]|e[^i]).*|ei¬(sch)|e?

Jetzt ein klein wenig komplizierter:

¬((le)?isch) = l(¬(eisch))|i(¬(sch))|([^le].*)? =
 = l(([^e]|e[^i]).*|ei¬(sch)|e?)|i(¬(sch))|([^le].*)? =
 = (l([^e]|e[^i]).*|lei¬(sch)|le?)|i(¬(sch))|([^le].*)? =
 = (l([^e]|e[^i]).*|(le)?i¬(sch)|le?)|([^le].*)?

Damit haben wir das Material für den gewünschten regulären Ausdruck:

¬(F(le)?isch) = F(¬((le)?isch))|([^F].*)? =
 = F((l([^e]|e[^i]).*|(le)?i¬(sch)|le?)|([^le].*)?)|([^F].*)? =
 = F((l([^e]|e[^i]).*|(le)?i(([^s]|s[^c]|sc[^h]|sch.).*
   |(sc?)?)|le?)|([^le].*)?)|([^F].*)?

Wir lernen daraus zum einen, dass die regulären Ausdrücke auch in ERE-Notation das Versprechen einhalten, dass mit jeder darstellbaren Menge von Zeichenreihen auch ihr Komplement darstellbar ist, zum anderen aber, dass das nicht gerade die Stärke dieser Notation ist. Die Programme, die mit regulären Ausdrücken arbeiten, haben deswegen Möglichkeiten, auch außerhalb des regulären Ausdrucks anzugeben, dass man das Komplement wünscht, z.B. die Option -v beim grep-Kommando.

Der wesentliche Grund für diese Beschränkung der regulären Ausdrücke dürfte darin liegen, dass man sie zur Mustersuche einsetzen will und es sinnlos ist, zu fragen, was man an einer bestimmten Stelle nicht gefunden hat. Für globale Fragestellungen vom ja/nein-Typ genügen aber Optionen außen im Kommando meistens.

Weitere theoretische Betrachtungen

Die folgenden Themen sollen in eine spätere Version des Artikels aufgenommen werden: