faecher:informatik:oberstufe:automaten:kellerautomaten:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung		 Vorhergehende Überarbeitung
Letzte ÜberarbeitungBeide Seiten der Revision
faecher:informatik:oberstufe:automaten:kellerautomaten:start [23.06.2022 08:18] – sbelfaecher:informatik:oberstufe:automaten:kellerautomaten:start [23.06.2022 08:21] – sbel
Zeile 16: Zeile 16:
 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. 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> </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? 
 +