Klammersprachen

Manche Sätze sind schwer zu verstehen, weil mehrere Nebensätze ineinander verschachtelt sind. Betrachte den folgenden Satz:

Der Hund, der die Katze, die eine Maus, die gerade ein Stück Käse, das gestern, als das Fußballspiel, das im Fernsehen gezeigt wurde, gerade zu Ende war, weggeworfen wurde, anbeißt, jagt, anbellt, heißt Bello.

Aufgabe 1

Welche vorderen Satzteile gehören zu welchen hinteren Satzteilen? Klicke zuerst auf einen Satzanfang und dann auf sein passendes Ende.

[1] Der Hund,
    [2] der die Katze,
        [3] die eine Maus,
            [4] die gerade ein Stück Käse,
                [5] das gestern,
                    [6] als das Fußballspiel,
                        [7] das im Fernsehen gezeigt wurde,
                    [6] gerade zu Ende war,
                [5] weggeworfen wurde,
            [4] anbeißt,
        [3] jagt,
    [2] anbellt,
[1] heißt Bello.

Die Satzteile im obigen Satz passen wie öffnende und schließende Klammern zusammen. Solche Strukturen begegnen dir auch in anderen Sprachen, beispielsweise bei geklammerten Rechenausdrücken, verschachtelten Wiederholungen in einem Programm und XML-Dokumenten.

Beim Prüfen solcher Ausdrücke muss erkannt werden, welche öffnenden und schließenden Elemente zusammengehören und ob sie richtig geschachtelt sind - wie bei Klammern bei mathematischen Ausdrücken. Sprachen mit solchen Strukturen bezeichnet man daher auch als "Klammersprachen"

Eine vereinfachte Klammersprache

Wir betrachten eine stark vereinfachte Klammersprache L_Klammer über dem Alphabet Σ = {(, )}. Ihre Wörter bestehen aus einer Folge öffnender Klammern, auf die genau so viele schließende Klammern folgen:

L_Klammer = {(), (()), ((())), (((()))), …}

Das folgende Syntaxdiagramm beschreibt die Sprache L_Klammer:

Die Wörter (() und ()) gehören nicht zur Sprache, weil die Anzahl öffnender und schließender Klammern verschieden ist. Auch ()() gehört nicht dazu: Der Ausdruck ist zwar korrekt geklammert, aber hier folgen nicht wie gefordert alle schließenden Klammern auf alle öffnenden Klammern

Aufgabe 2

1. Erstelle das Übergangsdiagramm eines deterministischen endlichen Automaten (DEA) mit dem Eingabealphabet Σ = {(, )}, der genau die Klammerausdrücke mit einer, zwei oder drei öffnenden Klammern und anschließend genauso vielen schließenden Klammern akzeptiert. Alle anderen Klammerausdrücke soll er ablehnen.
2. Erweitere dann DEA aus Teil (a) so, dass alle Worte der Sprache L_Klammer erkannt werden.

Grenzen endlicher Automaten

Um die Klammerausdrücke zu prüfen, muss sich ein Automat merken, wie viele Klammern noch geschlossen werden müssen. Bei einem endlichen Automaten übernehmen die Zustände dieses Merken. Für eine feste Obergrenze lässt sich ein passender Automat konstruieren. Die Sprache L_Klammer enthält jedoch Wörter mit beliebig vielen öffnenden Klammern.

Ein endlicher Automat hat nur endlich viele Zustände. Er kann deshalb nicht für jede mögliche Anzahl öffnender Klammern einen anderen Zustand erreichen. Daher kann er nicht alle Wörter dieser Sprache korrekt von Wörtern unterscheiden, die nicht dazugehören.

Ersetzt man in L_Klammer die die öffnende Klammer durch "a" und die schließende Klammer durch "b", lässt sich damit der folgende Satz formulieren:

Endliche Automaten können also manche formalen Sprachen erkennen, andere dagegen nicht. Formale Sprachen lassen sich danach unterscheiden, welche Regeln zu ihrer Beschreibung und welche Automatenmodelle zu ihrer Erkennung erforderlich sind. So entstehen unterschiedliche Sprachklassen. In den folgenden Abschnitten lernst du diese Klassen kennen und untersuchst, was die jeweiligen Automatenmodelle leisten können und wo ihre Grenzen liegen.