Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:automaten:kellerautomaten:start [21.11.2024 06:28] – [Aufgaben] Frank Schiebel
+++ faecher:informatik:oberstufe:automaten:kellerautomaten:start [11.02.2025 11:21] (aktuell) – [Aufgaben] Marco Kuemmel
@@ Zeile 5: / Zeile 5: @@
 === (A1) Vorüberlegungen ===
-**(A)** Konstruiere einen endlichen Automaten, der die Sprache L<sub>Klammer2</sub> aller Klammerausdrücke der Tiefe 2 erkennt.
+**(A)** Konstruiere einen endlichen Automaten, der die Sprache L<sub>Klammer2</sub> aller Klammerausdrücke bis zur Tiefe 2 erkennt.
 Zur Sprache gehören z.B.
   (()), ()(), (), (()())
@@ Zeile 44: / Zeile 44: @@
 Wir erweitern den endlichen Automaten um einen **Speicher**, der (potentiell) unbegrenzt viele Daten
-aufnehmen kann. Für kontextfreie Sprachen reicht als Speicher ein **Stack** -- dieser wird auch als "Keller" bezeichnet, aus diesem Grund nennt man solche um einen Stack erweiterten DEAs "Kellerautomat".
+aufnehmen kann. Für **kontextfreie Sprachen**((Kontextfreie Sprachen sind diejenigen, die von einem Kellerautomaten erkannt werden können.)) reicht als Speicher ein **Stack** -- dieser wird auch als "Keller" bezeichnet, aus diesem Grund nennt man solche um einen Stack erweiterten DEAs "Kellerautomat".
 Für unsere Klammersprache könnte ein erster Entwurf eines Kellerautomaten so aussehen - der Kellerspeicher ist hier mit 6 "Speicherplätzen" gezeichnet, kann aber durch weiteres "auf den Stack legen" beliebig erweitert werden:
@@ Zeile 50: / Zeile 50: @@
 {{ :faecher:informatik:oberstufe:automaten:kellerautomaten:ka01.drawio.png |}}
-Zu Beginn ist der Kellerspeicher leer - das wird durch das Symbol **#** gekennzeichnet - der Ablauf beginn beim markierten Startknoten. Der Automat befindet sich also zu Beginn im Zustand **q<sub>0</sub>,#**
+Zu Beginn ist der Kellerspeicher leer - das wird durch das Symbol **#** gekennzeichnet - der Ablauf beginnt beim markierten Startknoten. Der Automat befindet sich also zu Beginn im Zustand **q<sub>0</sub>,#**
 Um Komplikationen beim Aufschreiben der Klammern zu vermeiden, verwenden wir von nun an für eine öffnende Klammer das Symbol **a**, für eine schließende Klammer ein **z**. Wir wollen nun nachvollziehen, ob das Wort **aazazz** vom Automaten akzeptiert wird - und vor allem, was der Automat dabei alles "tun" muss.
@@ Zeile 265: / Zeile 265: @@
 Diese Sprache ist kontextfrei: beim Lesen von "a" wird ein Zeichen auf den Stack gelegt, bei Lesen von "b" bleibt der Stack unverändert und bei Lesen von "c" wird der Stack abgebaut. Da gleich viele "a" und "c" enthalten sein müssen, ist mindestens ein Kellerautomat notwendig -- die Sprache ist daher nicht regulär.
 ++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A5) Zusatzaufgabe ===
+Implementiere in Java zunächst einen endlichen Automaten der die Klammersprache L<sub>2</sub> aus dem Eingangsbeispiel erkennt, Arbeite mit a und z für Klammer auf und Klammer zu.
+  * Die Eingabe soll als Parameter beim Erstellen des Automaten erfragt werden.
+  * Modelliere die Zustände des Automaten und gib bei der Bearbeitung der Eingabe die Zustandswechsel auf den Konsole aus, so dass der Ablauf bei der Verarbeitung der Eingabe erkennbar ist.
+  * Erweitere den Automaten um einen Stack, um unendlichen Klammertiefen zu erkennen. Erstelle bei der Verarbeitung der Eingabe ein Ablaufdiagramm wie oben, das du auf der Konsole ausgibst.
+     - //Tipp 1: Importiere den Stack mit ''import java.util.Stack;'' und denke anschließend an das Initialisieren.//
+     - //Tipp 2: Um das oberste Element zu prüfen (ohne es zu entfernen), rufe ''peek()'' auf dem Stack auf.//
 ===== Material =====