Contents
Was sind Pushdown-Automaten?
Ein Pushdown-Automat ist im Wesentlichen ein endlicher Automat mit einer als Stack bezeichneten Hilfsdatenstruktur (zusätzlicher Speicher) , die Pushdown-Automaten hilft, kontextfreie Sprachen zu erkennen. Kellerautomaten werden in Theorien darüber verwendet, was von Maschinen berechnet werden kann. Sie sind leistungsfähiger als endliche Automaten, aber weniger leistungsfähig als Turing-Maschinen.
Ein Kellerautomat besteht aus drei Komponenten:
- Ein Eingabeband
- Ein Steuergerät
- Ein Stapel mit unendlicher Größe
Ein Stapel besteht aus einer endlichen Liste von Symbolen. Symbole können zur Liste hinzugefügt und aus ihr entfernt werden, jedoch nur an einem Ende der Liste. Das Ende der Liste, in dem Elemente hinzugefügt und entfernt werden können, wird als oberstes Ende des Stapels bezeichnet. Die Liste wird normalerweise als vertikaler ”Stapel” von Symbolen visualisiert, wobei Elemente oben hinzugefügt und entfernt werden.
Das Hinzufügen eines Symbols an der Spitze des Stapels wird als Verschieben eines Symbols auf den Stapel bezeichnet und das Entfernen eines Symbols wird als Herausnehmen eines Elements aus dem Stapel bezeichnet. Während jedes Schritts seiner Berechnung ist ein Pushdown-Automat in der Lage, mehrere Push- und Pop-Operationen auf seinem Stapel durchzuführen (dies zusätzlich zum möglicherweise Lesen eines Symbols aus der Eingabezeichenfolge, die vom Automaten verarbeitet wird).
Pushdown-Automaten können in Typen eingeteilt werden:
- Deterministische Pushdown-Automaten
- Nichtdeterministische Kellerautomaten
Deterministische Kellerautomaten können alle deterministischen kontextfreien Sprachen erkennen, während nichtdeterministische Kellerautomaten alle kontextfreien Sprachen erkennen können, wobei erstere häufig im Parserdesign verwendet werden.
Was Sie über Pushdown-Automaten wissen müssen
- Ein Kellerautomat (PDA) ist ein Automatentyp, der einen Stapel verwendet.
- Es hat den zusätzlichen Stack zum Speichern langer Buchstabenfolgen.
- Pushdown-Automaten können für Typ-2-Grammatik konstruiert werden.
- Eingabealphabete werden akzeptiert durch Erreichen von: Leerer Stack und Endzustand.
- Nicht-deterministische Pushdown-Automaten (NDPA) haben mehr Funktionen als deterministische Pushdown-Automaten (DPDA).
- Pushdown-Automaten können für kontextfreie Grammatik konstruiert werden.
- Nicht jeder nicht-deterministische Kellerautomat wird in seinen entsprechenden deterministischen Kellerautomaten umgewandelt.
Was sind endliche Automaten?
Ein endlicher Automat (FA) ist eine einfache idealisierte Maschine, die verwendet wird, um Muster in Eingaben zu erkennen, die aus einem Zeichensatz (oder Alphabet) stammen. Die Hauptfunktion eines endlichen Automaten besteht darin, eine Eingabe anzunehmen oder abzulehnen, je nachdem, ob das durch den FA definierte Muster in der Eingabe auftritt. Es hat eine Reihe von Zuständen und Regeln zum Wechseln von einem Zustand in einen anderen, hängt jedoch vom angewendeten Eingabesymbol ab. Im Grunde ist es ein abstraktes Modell eines digitalen Computers.
Ein endlicher Automat besteht aus:
- Endliche Menge von Zuständen
- Satz von Eingabesymbolen
- Ausgangszustand
- Satz von Endzuständen
- Übergangsfunktion
Finite Automaten werden in zwei Typen unterteilt:
- Deterministische endliche Automaten (DFA)
- Nicht-deterministische endliche Automaten (NFA)
Was Sie über Pushdown-Automaten wissen müssen
- Ein endlicher Automat (FA) ist eine einfache idealisierte Maschine, die verwendet wird, um Muster in Eingaben zu erkennen, die aus einem Zeichensatz stammen.
- Es hat weder die Fähigkeit noch den Platz, um lange Sequenzen von Eingabealphabeten zu speichern.
- Endliche Automaten können für Typ-3-Grammatik konstruiert werden.
- Eingabealphabete werden akzeptiert, wenn ”Endzustände” erreicht werden.
- Nicht-deterministische endliche Automaten (NFA) haben die gleichen Fähigkeiten wie deterministische endliche Automaten (DFA).
- Endliche Automaten können für reguläre Sprache konstruiert werden.
- Jeder nicht-deterministische endliche Automat wird in einen äquivalenten deterministischen endlichen Automaten umgewandelt.
Unterschied zwischen Kellerautomaten und endlichen Automaten
| VERGLEICHSGRUNDLAGE | PUSHDOWN-AUTOMATEN | FINITE AUTOMATA |
| Beschreibung | Ein Kellerautomat (PDA) ist ein Automatentyp, der einen Stapel verwendet. | Ein endlicher Automat (FA) ist eine einfache idealisierte Maschine, die verwendet wird, um Muster in Eingaben zu erkennen, die aus einem Zeichensatz stammen. |
| Platz | Es hat den zusätzlichen Stack zum Speichern langer Buchstabenfolgen. | Es hat weder die Fähigkeit noch den Platz, um lange Sequenzen von Eingabealphabeten zu speichern. |
| Konstruktion | Pushdown-Automaten können für Typ-2-Grammatik konstruiert werden. | Endliche Automaten können für Typ-3-Grammatik konstruiert werden. |
| Alphabete eingeben | Eingabealphabete werden akzeptiert durch Erreichen von: Leerer Stack und Endzustand. | Eingabealphabete werden akzeptiert, wenn ”Endzustände” erreicht werden. |
| Fähigkeit | Nicht-deterministische Pushdown-Automaten (NDPA) haben mehr Funktionen als deterministische Pushdown-Automaten (DPDA). | Nicht-deterministische endliche Automaten (NFA) haben die gleichen Fähigkeiten wie deterministische endliche Automaten (DFA). |
| Flexibilität | Pushdown-Automaten können für kontextfreie Grammatik konstruiert werden. | Endliche Automaten können für reguläre Sprache konstruiert werden. |
| Transformation | Nicht jeder nicht-deterministische Kellerautomat wird in seinen entsprechenden deterministischen Kellerautomaten umgewandelt. | Jeder nicht-deterministische endliche Automat wird in einen äquivalenten deterministischen endlichen Automaten umgewandelt. |