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?
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?
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 .
Es gibt mehrere mögliche Ebenen für Ihre Frage.
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:
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 .
OmG und Raphael haben Ihre Frage bereits beantwortet:
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.