Klammersprachen und Kellerautomaten

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

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

Die Sprache LKlammer wird oft auch etwas formaler in der folgenden Form dargestellt:

Lab = {anbn | n = 1, 2, 3, …}

Die öffnenden Klammern werden durch das Symbol a repräsentiert, die schließenden Klammern durch das Symbol b. Entscheidend ist auch hier, dass die Anzahl der schließenden Klammern genau der Anzahl der öffnenden Klammern entspricht.