Warum verwenden Pushdown-Automaten einen Stapel?

7

Ich nehme an einem Computertheoriekurs teil und mein Professor sagte uns, dass ein Pushdown-Automat keine anderen Datenstrukturen als einen Stapel (wie eine Warteschlange oder mehrere Stapel) verwenden kann. Warum ist das so?

gmelodie
quelle

Antworten:

15

Wenn Sie den Stapel in die Warteschlange oder in mehrere Stapel ändern, wird die Rechenleistung erhöht! (Wie Sie wissen, können wir eine Warteschlange mit zwei Stapeln modellieren). Wenn wir eine Warteschlange verwenden, kann diese als Turing-Maschine leistungsstark sein. Die Rechenleistung eines Push-Down-Automaten ist jedoch nicht so hoch! Mehr dazu erfahren Sie hier .

Oh mein Gott
quelle
37

Es gibt mehrere mögliche Ebenen für Ihre Frage.

  • Warum müssen PDAs einen Stapel haben? -- Per Definition! Ist einfach so.
  • Aber warum sind sie so definiert? - Jemand dachte, es könnte interessant werden. Und anscheinend war es so, weil viele Leute (sprich: das gesamte Feld) zugestimmt haben, diese Definition zu verwenden.
  • Warum ist es interessant? - Siehe die Antwort von reinierpost .
  • Warum unterrichtet mein Lehrer PDAs? - Das ist ein facettenreiches Thema. siehe hier für eine ähnliche Frage. Die Antworten übertragen sich.

Ich möchte die zweite Kugel etwas näher erläutern. Wie entstehen unterschiedliche Definitionen?

Wenn Sie mit verschiedenen Speichermodellen die endliche Kontrolle übernehmen, haben die resultierenden Klassen von Automaten sehr unterschiedliche Funktionen. Tatsächlich ist das ein großer Teil dessen, womit sich die Automatentheorie befasst. Sobald Sie erkennen, dass das Herumspielen mit Definitionen zu interessanten Konzepten führen kann, ist dies für Forscher nur natürlich - ein merkwürdiger Haufen! - um zu versuchen, den Raum möglicher Modelle zu erkunden.

Um nur einige Beispiele für Ideen aufzulisten, die Menschen hatten:

Und so weiter und so fort.

Beachten Sie, dass Sie auch andere Elemente ändern können:

  • Das Alphabet - machen Sie es unendlich oder kontinuierlich.
  • Die Übergangsfunktion - machen Sie es zu einer Beziehung oder erlauben Sie Übergänge.ε
  • Der Zustandssatz - machen Sie ihn unendlich oder erlauben Sie mehrere Startzustände.
  • Die Eingaben - machen sie unendlich oder Bäume oder zeitgesteuerte Sequenzen.
  • Zusätzliche Einschränkungen - Verwenden Sie Bänder, erlauben Sie jedoch nur Bewegungen in eine Richtung oder lassen Sie k-mal scannen (abwechselnd oder immer von links nach rechts?)

Interessante Dinge können passieren!

Das ist das Schöne an mathematischen Definitionen: Normalerweise bekommt man etwas . Dann können Sie viele Monate damit verbringen, herauszufinden, was Sie haben. Vielleicht ist es interessant, vielleicht auch nicht. Vielleicht ist es nützlich (eine gefürchtete Frage nach Gesprächen!), Vielleicht auch nicht. Aber es immer ist .

Raphael
quelle
27

OmG und Raphael haben Ihre Frage bereits beantwortet:

  • Pushdown-Automaten verwenden einen Stapel, weil sie so definiert sind
  • Wenn sie keinen Stapel verwenden würden, würden Sie einen anderen Automatentyp mit unterschiedlichen Eigenschaften erhalten

An dieser Stelle fragen Sie sich vielleicht: Warum präsentiert mein Professor den Pushdown-Automaten, nicht irgendeine andere Art von Automaten? Was macht den Pushdown-Automaten mit einem Stapel interessanter als einen Automaten mit einer anderen Datenstruktur?

Die Antwort ist, dass nicht deterministische Pushdown-Automaten genau die kontextfreien Sprachen erkennen können , die durch kontextfreie Grammatiken erzeugt werden , die in den 1950er Jahren in der Geschichte der Informatik als Technik zur Beschreibung der Syntax eingeführt wurden von Sprachen: sowohl natürliche Sprachen wie Englisch oder Russisch als auch Computersprachen wie Programmiersprachen (die erste Programmiersprache, die sie beschrieben haben, war FORTRAN ).

Das war damals eine große Sache. Kybernetik und Behaviorismus waren der Wahnsinn. Computer wurden allmählich kommerziell eingesetzt. Einer der Bereiche, auf die sie angewendet wurden, war die Sprachverarbeitung . Wie können wir Sprache beschreiben?

Nun, es besteht aus Äußerungen (Dinge, die Leute sagen oder aufschreiben), die aus Sequenzen von Gegenständen (Wörtern oder Tönen) bestehen. Eine Person, die etwas sagen will, wird diese Äußerungen ausstrahlen; eine andere Person empfängt sie und macht Sinn aus ihnen. Was ist, wenn wir einen Computer dazu bringen wollen, dasselbe zu tun? Wir müssen einen Weg finden, eine Sprache zu beschreiben, die einem Computer beigebracht werden kann. Wir brauchen eine Möglichkeit, gültige Äußerungen zu generieren, die ein Computer verwenden kann, und eine Möglichkeit, die Äußerungen zu erkennen, die ein Computer verwenden kann - so dass die Äußerungen tatsächlich die Äußerungen einer Sprache sind, die Menschen verwenden, wie z. B. Englisch oder Russisch.

Es gab bereits Beschreibungen von Geräten, die solche Dinge tun konnten: Es gab Zustandsautomaten und verschiedene Arten von Automaten. Allerdings Noam Chomsky , ein mathematischer Linguist am MIT beteiligt in einem mechanischen Übersetzungsprojekt realisierten Zustandsmaschinen sind nicht stark genug , um natürliche Sprachen wie Englisch zu beschreiben, wie sie das Phänomen nicht beschreiben können Rekursion in Sprache . Er brauchte etwas Ähnliches, aber mit der Fähigkeit, die Rekursion zu beschreiben, und kam zu den kontextfreien Grammatiken . Er bewies, dass diese tatsächlich mehr Sprachen beschreiben können als Zustandsmaschinen, aber weniger als einige andere Techniken - ein Ergebnis, das als Chomsky-Hierarchie bekannt ist. Er hoffte, sie würden Sprachen wie Englisch und Russisch beschreiben.

Kontextfreie Grammatiken erzeugen Äußerungen. Chomsky glaubte, sie hätten im Grunde beschrieben, wie eine Person beim Sprechen Sätze erzeugt. Sie benötigen auch ein Gerät, um zu beschreiben, wie Äußerungen erkannt werden. Das ist , was Kellerautomaten sind für. Sie können genau die Äußerungen erkennen, die durch eine kontextfreie Grammatik erzeugt werden. Es wurde daher angenommen, dass sie im Grunde beschreiben, wie ein Mensch Sätze beim Hören erkennt.

Bald darauf stellte sich heraus, dass kontextfreie Sprachen die Syntax von Sprachen nicht vollständig beschreiben können - Sie benötigen alle Arten von zusätzlichen Maschinen, um dies richtig zu tun. Dies gilt sowohl für natürliche als auch für künstliche Sprachen. (Um ehrlich zu sein, ich denke, Chomsky wollte sich sichtbar Pushdown-Sprachen einfallen lassen , außer dass er den Unterschied nicht erkannte, und wenn er es getan hätte, hätte es uns allen viel Ärger erspart.)

Kontextfreie Sprachen und Pushdown-Automaten sind jedoch mathematisch sehr einfache und elegante Geräte, und die Chomsky-Hierarchie ist ein einfaches und elegantes Ergebnis. Daher sind sie in der Ausbildung sehr nützlich, um die Grundlagen der computergestützten Sprachbeschreibung und -erkennung ( formale Sprache) zu erklären Theorie ). Aus diesem Grund sind sie weiterhin ein Standardbestandteil des theoretischen Lehrplans für Informatik, und viele in der Praxis verwendete Techniken basieren auf ihnen. Daher sind sie wirklich die erforderlichen Kenntnisse, wenn Sie etwas im Zusammenhang mit der Verarbeitung natürlicher Sprache und der Programmiersprache lernen möchten Implementierung und andere sprachbezogene Themen.

Reinierpost
quelle