Kellerautomaten

Wiederholung

Kellerautomaten

Kurzerklärung

Ein Kellerautomat (Pushdown Automaton, PDA) ist ein spezieller Typ von endlichem Automaten, der zusätzlich einen Stack (Keller) als Speichermedium nutzt. Diese Erweiterung ermöglicht es dem Automaten, kontextfreie Sprachen zu akzeptieren. Der Kellerautomat kann auf Symbole auf dem Keller zugreifen und diese gemäß einer Übergangsfunktion manipulieren, um Eingaben zu verarbeiten und zu entscheiden, ob sie zu einer bestimmten Sprache gehören.

In der Theorie der formalen Sprachen wird ein Kellerautomat typischerweise als 6-Tupel definiert:

$$M=(Z,\Sigma ,\Gamma ,\delta ,z_0,\#)$$

• $Z$ ist eine endliche Menge von Zuständen.
• $\Sigma$ ist das (endliche) Eingabealphabet.
• $\Gamma$ ist das (endliche) Kelleralphabet.
• $\delta$ ist die Übergangsfunktion: $$\delta :Z\times (\Sigma \cup \{\epsilon \})\times \Gamma \to \mathcal{P}(Z\times {\Gamma }^{\ast })$$
• $z_0$ ist der Startzustand.
• $\#$ ist das Startsymbol im Keller.

Funktionsweise eines Kellerautomaten

Ein Kellerautomat arbeitet, indem er die Eingabezeichen liest und gleichzeitig den Zustand und den Inhalt des Kellers entsprechend der Übergangsfunktion $\delta$ aktualisiert. Die Übergangsfunktion bestimmt, welche Aktionen der Automat ausführt, basierend auf dem aktuellen Zustand, dem aktuellen Eingabezeichen (oder dem leeren Wort $\epsilon$), und dem Symbol am oberen Ende des Kellers. Der Automat akzeptiert eine Eingabe entweder durch Erreichen eines akzeptierenden Zustands oder durch Leeren des Kellers.

Komponenten und Übergänge

1. Zustände ($Z$): Diese repräsentieren die verschiedenen Konfigurationsmöglichkeiten des Automaten. Der Automat wechselt zwischen diesen Zuständen gemäß den Regeln der Übergangsfunktion.
2. Eingabealphabet ($\Sigma$): Dies ist die Menge der Symbole, die der Automat aus der Eingabe lesen kann.
3. Kelleralphabet ($\Gamma$): Dies ist die Menge der Symbole, die der Automat im Keller speichern kann.
4. Übergangsfunktion ($\delta$): Diese Funktion beschreibt, wie der Automat von einem Zustand in einen anderen übergeht, wie er Symbole vom Keller entfernt und welche Symbole er auf den Keller schreibt.
5. Startzustand ($z_0$): Der Zustand, in dem der Automat beginnt.
6. Startkellersymbol ($\#$): Das Symbol, das initial im Keller liegt.

Beispiel eines Kellerautomaten

Angenommen, wir haben die Sprache L = \{a^{2n}\a^n \mid n \in\mathbb{N}_{\gt0}}, die aus Wörtern besteht, bei denen vor einem Dollarzeichen \ doppelt so viele $a$s wie danach stehen.

Ein Kellerautomat, der diese Sprache akzeptiert, könnte wie folgt definiert werden:

• Zustände: $Z=\{q_0,q_1,q_2,q_f\}$
• Eingabealphabet: \Sigma = \{a, \}$
• Kelleralphabet: $\Gamma =\{a,\#\}$
• Startzustand: $z_0=q_0$
• Startkellersymbol: $\#$
• Akzeptierende Zustände: $F=\{q_f\}$

Übergangsfunktion ($\delta$):

1. Initiale Phase (Doppelte $a$s auf den Keller legen):

   • $\delta (q_0,a,\#)=\{(q_0,a\#)\}$
   • $\delta (q_0,a,a)=\{(q_0,aa)\}$

2. Dollarzeichen erkennen:

   • \delta(q_0, \, a) = {(q_1, a)}$

3. $a$s nach dem Dollarzeichen verarbeiten:

   • $\delta (q_1,a,a)=\{(q_1,\epsilon )\}$

4. Keller entleeren und akzeptieren:

   • $\delta (q_1,\epsilon ,\#)=\{(q_f,\#)\}$

Erklärung der Funktionsweise:

1. Phase 1 (Initiale Phase):

   • Der Automat beginnt im Zustand $q_0$ und liest $a$s, wobei er jedes $a$ auf den Keller legt. Dadurch wird sichergestellt, dass die Anzahl der $a$s im Keller doppelt so groß ist wie die Anzahl der $a$s, die nach dem Dollarzeichen gelesen werden müssen.

2. Phase 2 (Dollarzeichen erkennen):

   • Sobald der Automat das Dollarzeichen \$$ liest, wechselt er in den Zustand q_1$,umdienachfolgenden$a$s zu verarbeiten.

3. Phase 3 (Nachfolgende $a$s verarbeiten):

   • Im Zustand $q_1$ liest der Automat jedes $a$ und entfernt ein $a$ vom Keller. Dies stellt sicher, dass die Anzahl der $a$s nach dem Dollarzeichen korrekt ist.

4. Phase 4 (Akzeptieren):

   • Wenn alle $a$s nach dem Dollarzeichen verarbeitet wurden und der Keller das Startsymbol $\#$ enthält, wechselt der Automat in den akzeptierenden Zustand $q_f$ und akzeptiert die Eingabe.

Fazit

Ein Kellerautomat erweitert die Fähigkeiten eines endlichen Automaten durch die Nutzung eines Stacks, was ihn besonders mächtig für die Erkennung kontextfreier Sprachen macht. Durch die Verwendung des Kellers kann der Automat eine größere Bandbreite an Sprachen verarbeiten, indem er sich an eine theoretisch unendliche Menge von Informationen erinnert und diese entsprechend manipuliert.

Indem Sie diesen Aufbau und die Übergangsregeln verstehen, können Sie komplexe formale Sprachen definieren und Automaten entwickeln, die diese Sprachen korrekt akzeptieren.

---

Kellerautomat aufstellen

Ablauf zur Erstellung eines Kellerautomaten

1. Bestimmen Sie das Eingabealphabet: Legen Sie die Menge der Terminalsymbole fest, die in der Sprache verwendet werden können.
2. Identifizieren Sie die Sprachstruktur: Überlegen Sie, welche Muster und Strukturen in der Sprache vorhanden sein sollen. Handelt es sich um einfache Wiederholungen, Verschachtelungen, spezielle Sequenzen oder andere Regularitäten?
3. Definieren Sie die Zustände: Bestimmen Sie eine endliche Menge von Zuständen, die der Automat durchlaufen kann.
4. Bestimmen Sie das Kelleralphabet: Legen Sie die Menge der Symbole fest, die im Keller verwendet werden können.
5. Wählen Sie den Startzustand und das Startkellersymbol: Bestimmen Sie den Zustand, in dem der Automat beginnt, und das Symbol, das initial im Keller liegt.
6. Entwickeln Sie die Übergangsfunktion: Schreiben Sie eine Reihe von Regeln, die festlegen, wie der Automat anhand des aktuellen Zustands, des gelesenen Eingabezeichens und des Kellersymbols den neuen Zustand und die Kelleroperation bestimmt.
7. Definieren Sie die akzeptierenden Zustände: Bestimmen Sie, welche Zustände akzeptierend sind und unter welchen Bedingungen die Eingabe akzeptiert wird.
8. Überprüfen Sie den Automat:
   • Stellen Sie sicher, dass der Automat alle Wörter der Sprache akzeptieren kann.
   • Prüfen Sie, ob der Automat keine Wörter akzeptiert, die nicht zur Sprache gehören.
9. Dokumentieren Sie den Automat: Erklären Sie die Funktion jeder Übergangsregel und wie sie zur Verarbeitung der Sprache beiträgt.

Indem Sie diesen Ablauf befolgen, können Sie einen klaren und präzisen Kellerautomaten erstellen, der eine formale Sprache innerhalb des Rahmens der formalen Sprachtheorie akzeptiert.

Beispiel aus [[FSK-ÜB-6#b-geben-sie-einen-kellerautomaten-an-der-l-akzeptiert-mit-leerem-keller-oder-mit-endzuständen-erklären-sie-kurz-warum-ihr-automat-genau-l-akzeptiert|b) Geben Sie einen Kellerautomaten an, der $L$ akzeptiert (mit leerem Keller oder mit Endzuständen). Erklären Sie kurz, warum Ihr Automat genau $L$ akzeptiert.]]

Um die angegebene Aufgabe zu lösen, bei der ein Kellerautomat für die Sprache L = \{a^{2n}\a^n \mid n \in \mathbb{N}_{\gt0}}$ erstellt werden soll, gehen Sie folgendermaßen vor:

1. Definieren Sie das Eingabealphabet: Hier ist das Eingabealphabet \Sigma = \{a, \}$ bereits gegeben.

2. Identifizieren Sie das Muster der Sprache: Die Sprache $L$ besteht aus einer Sequenz von $2n$ ‘a’s, gefolgt von einem ‘${}^{\prime },gefolgtvon$n${}^{\prime }{a}^{\prime }s.Dabeiist$n$ eine positive natürliche Zahl.

3. Erstellen Sie die Zustände: Für die Sprache $L$ benötigen Sie eine Menge von Zuständen $Z=\{q_0,q_1,q_f\}$.

4. Bestimmen Sie das Kelleralphabet: Das Kelleralphabet $\Gamma$ könnte aus den Symbolen $\{a,\#\}$ bestehen, wobei $#` das Startkellersymbol ist.

5. Wählen Sie den Startzustand und das Startkellersymbol: Der Startzustand ist $z_0=q_0$ und das Startkellersymbol ist $\#$.

6. Entwickeln Sie die Übergangsfunktion:

   • Initiale Phase (Doppelte $a$s auf den Keller legen):
     • $\delta (q_0,a,\#)=\{(q_0,a\#)\}$
     • $\delta (q_0,a,a)=\{(q_0,aa)\}$
   • Dollarzeichen erkennen:
     • \delta(q_0, \, a) = {(q_1, a)}$
   • $a$s nach dem Dollarzeichen verarbeiten:
     • $\delta (q_1,a,a)=\{(q_1,\epsilon )\}$
   • Keller entleeren und akzeptieren:
     • $\delta (q_1,\epsilon ,\#)=\{(q_f,\#)\}$

7. Definieren Sie die akzeptierenden Zustände: Der akzeptierende Zustand ist $q_f$.

Erklärung der Übergangsregeln

• $\delta (q_0,a,\#)=\{(q_0,a\#)\}$: Wenn der Automat im Zustand $q_0$ ist, ein ‘a’ liest und das Kellersymbol $\#$ sieht, dann bleibt er im Zustand $q_0$ und schiebt ein ‘a’ auf den Keller.
• $\delta (q_0,a,a)=\{(q_0,aa)\}$: Wenn der Automat im Zustand $q_0$ ist, ein ‘a’ liest und ein ‘a’ auf dem Keller liegt, dann bleibt er im Zustand $q_0$ und schiebt ein weiteres ‘a’ auf den Keller.
• **\delta(q_0, \, a) = {(q_1, a)}$\ast \ast :WennderAutomatimZustand$q_0$ist,ei{n}^{\prime }$’ liest und ein ‘a’ auf dem Keller liegt, dann wechselt er in den Zustand $q_1$ und behält das ‘a’ auf dem Keller.
• $\delta (q_1,a,a)=\{(q_1,\epsilon )\}$: Wenn der Automat im Zustand $q_1$ ist, ein ‘a’ liest und ein ‘a’ auf dem Keller liegt, dann bleibt er im Zustand $q_1$ und entfernt das ‘a’ vom Keller.
• $\delta (q_1,\epsilon ,\#)=\{(q_f,\#)\}$: Wenn der Automat im Zustand $q_1$ ist und das Kellersymbol $\#$ sieht, dann wechselt er in den Zustand $q_f$ und akzeptiert die Eingabe.

Zusammengenommen bedeuten diese Regeln, dass der Automat mit dem Lesen der $a$s beginnt und diese auf den Keller legt, bis er das '${}^{\prime }liest.NachdemLesende{s}^{\prime }$' wechselt der Automat in den Zustand $q_1$ und entfernt die ‘a’s vom Keller, während er die verbleibenden ‘a’s in der Eingabe liest. Wenn der Keller leer ist und das Startkellersymbol $\#$ erreicht wird, akzeptiert der Automat die Eingabe.

Indem Sie diesen Ablauf befolgen, können Sie einen Kellerautomaten erstellen, der die Sprache $L$ akzeptiert, indem er die Struktur der Eingabezeichenfolge überprüft und die korrekte Anzahl und Reihenfolge der Symbole sicherstellt.

---