Ausblick - Theoriebildung

Probleme als Ausgangspunkt für Theoriebildung

Probleme, die sich nur schwer oder auch gar nicht lösen lassen, bilden oft den Ausgangspunkt für vertiefende Studien. Wenn es einem dabei gelingt, eine Theorie zum Gegenstandsbereich zu entwickeln, gewinnt man oft auch Klarheit bzgl. der gewünschten Problemlösungen.

Die beiden folgenden Probleme sollen eine solche Theoriebildung motivieren. In den folgenden Abschnitten werden die Theoriebausteine entwickelt, die zu den Lösungen der Probleme führen.

Spracherkennung bei Klammersprachen / Spracherkennung mit Kellerautomaten

Im Abschnitt Beispiele für Klammersprachen haben wir verschiedene Sprachen betrachtet, bei denen eine korrekte Klammerung eine wichtige Rolle spielt.

Beispiel: Die Sprache L_RA der vereinfachten Rechenausdrücke

Zu dieser Sprache gehören Wörter wie z.B. z*(z+z) und z+z*(z+z). Hier eine Grammatik zu dieser Sprache:

A -> A + S
A -> S
S -> S * F
S -> F
F -> ( A )
F -> z 

Beispiel: Die Sprache L_RP der vereinfachten Roboterprogramme

Zu dieser Sprache gehören Wörter wie z.B. eesbsbe*e*. Hier eine Grammatik zu dieser Sprache:

P -> F
F -> A
F -> AF
A -> e
A -> sbF*

Beispiel: Die Sprache L_MyXML der vereinfachten XML-artigen Ausdrücke

Zu dieser Sprache gehören Wörter wie z.B. <ab>acaa</ab>. Hier eine Grammatik zu dieser Sprache:

S -> <aat>
S -> <bbt>
T -> aAT
T -> bBT
T -> M
Aa -> aA
Ab -> bA
AM -> Ma
Ba -> aB
Bb -> bB
BM -> Mb
M -> >N
N -> aN
N -> bN
N -> cN
N -> <!--
</code-->
</bbt></aat>

Problem: Erkennung von Klammersprachen

Können alle diese Klammersprachen von Kellerautomaten erkannt werden?

Problem: Spracherkennung mit Kellerautomaten

Welche Sprachen kann man mit Kellerautomaten erkennen? Kann man es einer Grammatik ansehen, ob die zugehörige Sprache von einem Kellerautomaten erkannt werden kann?