25.6 Reguläre Sprachen

Definition

Was eine reguläre Sprache ist, kann man sehr schnell definieren:

Reguläre Sprachen sind all die Sprachen, die von determinierten endlichen Automaten akzeptiert werden.

Beispiele

Beispiele hatten wir ja schon kennengelernt:

• Java-Bezeichner
• int-Zahlen
• double-Zahlen

Hier ein etwas komplexeres Beispiel aus der alten Version meines Kurses: Pascal-Prozedurköpfe:

Ein DEA für Prozedurköpfe der Sprache Pascal

Dieser Automat akzeptiert Prozedurköpfe (Signaturen) der Sprache Pascal, die leider nicht mehr unterrichtet wird. Hier ein paar Beispiele für solche Prozedurköpfe:

• procedure gibErgebnis(var ergebnis : real);
• procedure einfach(var x,y,z:integer);
• procedure komplexer(x,y,z : integer; r1, r2 : real);
• procedure ganzkomplex(x,y,z : integer; var ergebnis : real; r1,r2 : real);

Grenzen

Sie sehen, dass reguläre Ausdrücke wie zum Beispiel Pascal-Prozedurköpfe ganz schön komplex werden können (wie komplex das werden kann, sehen Sie auf der entsprechenden Seite der Wikipedia oder auf der Seite vom Leibniz-Rechenzentrum). Dennoch gehören reguläre Ausdrücke zu den einfachsten Sprachen überhaupt.

Nun wird es aber interessant! Schauen Sie sich die folgenden "Ausdrücke" an:

3
3+4
3+4*5
(3+4)*5
((3+4)*5+6)*(7+8)

All diese Ausdrücke gehören zur Klasse der "arithmetischen Ausdrücke". Wenn Sie jetzt versuchen, einen determinierten endlichen Automaten zu konstruieren, der solche Ausdrücke mit beliebig vielen Klammerpaaren akzeptiert, werden sie scheitern. Es wird Ihnen nicht gelingen!

Ein DEA kann nicht zählen!

Für jede geöffnete Klammer eines arithmetischen Ausdrucks muss eine geschlossene Klammer vorhanden sein. Ein Ausdruck wie

(3+4

wäre zum Beispiel nicht korrekt, denn die schließende Klammer fehlt.

Der folgende DEA akzeptiert arithmetische Ausdrücke mit maximal zwei Klammerebenen:

Ein DEA für arithmetische Ausdrücke mit zwei Klammerebenen

Ein DEA für Ausdrücke mit maximal drei Klammerebenen wäre um eine "Etage" höher und so weiter. Aber es wird Ihnen nicht gelingen, einen DEA für Ausdrücke mit beliebig vielen Klammerebenen zu konstruieren, der eine endliche Zahl von Zuständen besitzt.

In der nächsten Folge werden wir sehen, wie man dieses wichtige Problem lösen kann.