Spracherkennung bei Klammersprachen

Klammerausdrücke

Allen Klammersprachen ist gemeinsam, dass es zu jeder öffnenden Klammer eine korrespondierende schließende Klammer geben muss. Wir betrachten im Folgenden nur noch diese zentrale Eigenschaft von Klammersprachen.

Wir erfassen diese Eigenschaft mit ganz einfachen Klammerausdrücken, die wie folgt aufgebaut sind:

(), (()), ((())), ... .

Die Sprache L_Klammer soll alle solche Klammerausdrücke erfassen, bei denen nach einer Folge öffnender Klammern genau so viele schließende Klammern folgen.

Nicht zur Sprache L_Klammer gehören z.B. die Klammerausdrücke (() und (()))). Ebenfalls nicht zu dieser sehr einfachen Sprache gehört der Klammerausdruck ()().

In Abschnitt Exkurs - Grenzen von endlichen Automaten wurde gezeigt, dass die so definierte Sprache der Klammerausdrücke nicht mit einem endlichen Automaten erkannt werden kann.

Ein Verarbeitungsmodell zur Erkennung von Klammerausdrücken

Das Verarbeitungsmodell endlicher Automat muss erweitert werden, um in der Lage zu sein, Klammerausdrücke zu erkennen. Die folgende Abbildung zeigt - in wesentlichen Zügen - ein solches erweitertes Verarbeitungsmodell.

Aufgabe 1

Wie funktioniert das erweiterte Verarbeitungsmodell? Welche Funktion hat der integrierte Stapel (man nennt ihn auch Keller)? Woran erkennt die Verarbeitungseinheit, ob ein Klammerausdruck korrekt ist?