faecher:informatik:oberstufe:automaten:kellerautomaten:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.

====== Klammersprachen und Kellerautomaten ======

Die Sprache **L<sub>Klammer</sub>** soll alle solche Klammerausdrücke enthalten, bei denen nach einer Folge öffnender Klammern genau so viele schließende Klammern folgen. 

Nicht zur Sprache L<sub>Klammer</sub> gehören z.B. die Klammerausdrücke 
  (() 
und 
  (())))
Ebenfalls nicht zu dieser Sprache gehört der Klammerausdruck ''()()''. 
<WRAP center round tip 90%>

Die Sprache L<sub>Klammer</sub> wird oft auch etwas formaler in der folgenden Form dargestellt: 

L<sub>ab</sub> = {a<sup>n</sup>b<sup>n</sup> | n = 1, 2, 3, ...}

Die öffnenden Klammern werden durch das Symbol ''a'' repräsentiert, die schließenden Klammern durch das Symbol ''b''. Man erkennt, dass es sich nicht unbedingt um Klammern handeln muss. Entscheidend ist, dass die Anzahl der ''b'' genau der Anzahl der zuvor aufgetretenen ''a'' entspricht.
</WRAP>

----
{{:aufgabe.png?nolink  |}}
=== (A1) Vorüberlegungen ===

**(a)** Konstruiere einen endlichen Automaten, der die Sprache L<sub>Klammer2</sub> aller Klammerausdrücke der Tiefe 2 erkennt. 
Zur Sprache gehören z.B. 		
  (()), ()(), (), (()())
Nicht zur Sprache gehören z.B. 	
  ((()), ((())), ()), )(, )()(

**(b)** Gibt es einen endlichen Automaten A, der die Sprache  L<sub>ab</sub> = {a<sup>n</sup>b<sup>n</sup> | n = 1, 2, 3, ...} erkennt?