Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:automaten:kellerautomaten:start [18.11.2024 18:33] – [Ablaufprotokoll eines Kellerautomaten] 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 11: / Zeile 11: @@
   ((()), ((())), ()), )(, )()(
-**(B)** Gibt es einen endlichen Automaten A, der die Sprache  L<sub>ab</sub> = {(<sup>n</sup>)<sup>n</sup> | n = 1, 2, 3, ...} erkennt? Wie sehen diese aus und worin unterscheiden sich die Automaten, die unterschiedliche Klammerungstiefen erkennen?
+**(B)** Gibt es einen endlichen Automaten A, der die Sprache  L<sub>()</sub> = {(<sup>n</sup>)<sup>n</sup> | n = 1, 2, 3, ...} erkennt? Wie sehen diese aus und worin unterscheiden sich die Automaten, die unterschiedliche Klammerungstiefen erkennen?
 **(C)** Gib einen endlichen Automaten A an, der die allgemeine Klammersprache, also Klammerungen beliebiger Tiefe erkennt - siehst du ein Problem?
@@ Zeile 33: / Zeile 33: @@
 <callout type="alert">
 ++++ Erkenntnis zu (C) |
-Versuche, einen solchen endlichen Automaten A zu konstruieren, scheitern an der Unmöglichkiet, die Anzahl der öffnenden Klammern im Automaten mitzuzählen.
+Versuche, einen solchen endlichen Automaten A zu konstruieren, scheitern an der Unmöglichkeit, die Anzahl der öffnenden Klammern im Automaten mit zu zählen.
-Die **Endlichkeit** eines endlichen Deterministische Automaten besteht in der **Endlichkeit der Zustände** – um "zählen" zu können, wie viele Klammern bereits geöffnet wurden und damit auch wieder geschlossen werden müssen, braucht man aber genau einen Zustand mehr als die Klammertiefe beträgt. Ist diese aber beliebig, so ist kein Automat mit endlich vielen Zuständen konstruierbar.
+Die **Endlichkeit** eines endlichen Deterministische Automaten besteht in der **Endlichkeit der Zustände** – um "zählen" zu können, wie viele Klammern bereits geöffnet wurden und damit auch wieder geschlossen werden müssen, braucht man genau einen Zustand mehr als die Klammertiefe beträgt. Ist diese  beliebig, so ist kein Automat mit endlich vielen Zuständen konstruierbar.
-Wichtig ist der **Unterschied zur Eingabelänge** der gültigen Wörtern eine Sprache, die durch einen endlöichen Automaten  erkannt werden kann: Diese kann sehr wohl unendlich lang sein – das äußert sich lediglich dartin, dass der Automat in Schliefen wiederholt duchlaufen wird, bis er am Ende des Eingabeworts an einen akzeptierenden Endzustand gelangt.
+Wichtig ist der **Unterschied zur Eingabelänge** der gültigen Wörtern eine Sprache, die durch einen endlichen Automaten  erkannt werden kann: Diese kann sehr wohl unendlich lang sein – das äußert sich lediglich darin, dass der Automat in Schleifen wiederholt durchlaufen wird, bis er am Ende des Eingabeworts an einen akzeptierenden Endzustand gelangt.
 ++++
 </callout>
@@ 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 175: / Zeile 175: @@
 Eingabe endet, q0 ist Endzustand: Wort wird akzeptiert!
+===== Aufgaben =====
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A2) Vorüberlegungen ===
+=== (A2) ===
 {{ :faecher:informatik:oberstufe:automaten:kellerautomaten:flaci_ka.png?300|}}
   * Simuliere den Klammerautomaten in FLACI.
-  * Teste den Automaten mit verschiedenen Eingaben und volziehe seine Funktionsweise nach.
+  * Teste den Automaten mit verschiedenen Eingaben und vollziehe seine Funktionsweise nach.
 **Hinweise**
@@ Zeile 197: / Zeile 201: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A3) Vorüberlegungen ===
+=== (A3) ===
 Gegeben sind folgende Kellerautomaten. Beschreibe für jeden der Automaten die Wörter, die dieser erkennt und erstelle jeweils Ablaufprotokolle für zwei aussagekräftige Beispieleingaben – ein Wort, das akzeptiert wird und eines, das verworfen wird.
@@ Zeile 207: / Zeile 211: @@
 {{ :faecher:informatik:oberstufe:automaten:kellerautomaten:ka_a42.png |}}
+**(C)**
+{{ :faecher:informatik:oberstufe:automaten:kellerautomaten:ka_43.png |}}
+++++ Lösung (A) |
+L = { a<sup>n</sup>b<sup>n</sup> | n > 0 } -> Wörter mit einer Anzahl n von "a" gefolgt von derselben Anzahl "b".
+{{ :faecher:informatik:oberstufe:automaten:kellerautomaten:lsga.png |}}
+++++
+++++ Lösung (B) |
+L = { a<sup>n</sup>b<sup>n</sup> | n ≥ 0 } -> Wörter mit einer Anzahl "a" gefolgt von derselben Anzahl "b" – das leere Wort ist Teil der Sprache.
+{{ :faecher:informatik:oberstufe:automaten:kellerautomaten:lsgb.png |}}
+Am Ende der Eingabe wird also immer versucht, mittels λ-Übergang abzuschließen. Dabei landet man entweder im akzeptierenden Zustand q<sub>0</sub> (wenn ein # auf dem Stack liegt, dieser also leer ist) oder aber im Fehlerzustand q<sub>F</sub> (wenn der Stack nicht leer ist, dort also ein anderes Zeichen als der Stackboden # obenauf liegt).
+++++
+++++ Lösung (C) |
+L = { a<sup>n</sup>b<sup>m</sup>c<sup>n</sup> | n,m > 0 } -> Wörter mit einer Anzahl "a" gefolgt von beliebig vielen b, gefolgt von derselben Anzahl "c" wie zu Beginn "a" vorhanden waren.
+{{ :faecher:informatik:oberstufe:automaten:kellerautomaten:lsgc.png |}}
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A4) ===
+Entscheide mit Hilfe eines Kellerautomaten, ob die folgenden Sprachen kontextfrei sind. Sprachen sind kontextfrei, wenn sie von einem Kellerautomaten erkannt werden können. Wenn die Sprache kontextfrei ist, dann erläutere, wie der Kellerautomat arbeiten würde. Falls nicht, dann begründe, warum sie nicht mit einem Kellerautomaten erkannt werden kann.
+  * **(A)** L = { a<sup>n</sup>b<sup>n</sup> | n ≥ 0 }
+  * **(B)** L = { a<sup>n</sup>b<sup>n</sup>c<sup>n</sup> | n ≥ 0 }
+  * **(C)** L = { w ∈ {a, b}* | #a = #b } die alle Wörter enthält, die aus gleich vielen a und b bestehen, die – im Gegensatz zur Sprache aus Aufgabenteil a) - in beliebiger Reihenfolge auftreten dürfen. (Hinweis: #a bezeichnet die Anzahl der a´s in dem betreffenden Wort.)
+  * **(D)** L = { a<sup>n</sup>b<sup>m</sup>c<sup>n</sup> | n, m ≥ 0 }
+++++ Lösung 4(A) |
+Die Sprache ist kontextfrei (aber nicht regulär) – für jedes "a" der Eingabe legt man einen Marker auf den Keller, für jedes  "b" nimmt man einen herunter. Ist der Keller am Ende leer, wird das Wort akzeptiert.
+++++
+++++ Lösung 4(B) |
+Die Sprache ist nicht kontextfrei – dies ist leicht einzusehen, wenn man versucht, festzulegen, wann der Stack auf- und wann er abgebaut wird. Man wird annehmen, dass "a" den Stack aufbaut. Dann könnte "b" den Stack abbauen, aber für "c" gibt es damit keine Zählmöglichkeit mehr. Wir würden also einen weiteren Stack benötigen, um diese Sprache zu erkennen. Dann könnte man auf beide Stacks bei Lesen von "a" ein Zeichen legen und bei Lesen von "b" Stack 1, bei Lesen von "c" Stack 2 abbauen.
+++++
+++++ Lösung 4(C) |
+Diese Sprache ist kontextfrei. Man kann mit zwei Zeichen im Stackalphabet arbeiten: ist ein "a" auf dem Stack und kommt ein weiteres "a", wird dieses obenauf gelegt. Folgt hingegen ein "b", wird das "a" abgebaut. Ist bei Eingabe "b" kein "a" zum abbauen vorhanden, wird das "b" auf den Stack gelegt und seinerseits von "a"s abgebaut.
+++++
+++++ Lösung 4(D) |
+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 =====
+   * [[https://slides.info-bw.de/fs-wiki-kellerautomaten/|Präsentation: Kellerautomaten]] [[https://slides.info-bw.de/fs-wiki-kellerautomaten/?print-pdf|(PDF)]]((Link öffnen, dann aus dem Browser in ein PDF drucken)) [[https://codeberg.org/slides-fs/fs-wiki-kellerautomaten|(Code)]]