Contents
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 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 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.
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:
Finite Automaten werden in zwei Typen unterteilt:
| 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. |
Einleitung: Die Begriffe "Freeway" und "Highway" werden oft synonym verwendet, aber es gibt subtile Unterschiede…
Burritos und Enchiladas sind zwei beliebte Gerichte der mexikanischen Küche, die oft miteinander verwechselt werden.…
In der Zellbiologie spielen Replikation und Transkription entscheidende Rollen im genetischen Prozess. Beide sind Mechanismen,…
Osmose und Diffusion sind zwei grundlegende Prozesse, die in der Zellbiologie und Chemie eine entscheidende…
Einleitung: Die Evolution der mobilen Kommunikationstechnologie hat einen bedeutenden Meilenstein erreicht, als 4G (LTE) zu…
Einleitung: JPG und PNG sind zwei gängige Bildformate, die im Internet weit verbreitet sind. Obwohl…