So rufen Sie eine strukturierte Sprache auf, die keine Schleife oder eine funktionale Sprache, die nicht zurückkehren kann

Question

Ich habe eine spezielle "Programmiersprache" erstellt, die absichtlich nicht zweimal den gleichen Code bewerten kann (dh es kann nicht schleifen). Es wird im Wesentlichen durchgeführt, um einen fließendchartähnlichen Prozess zu beschreiben, bei dem jedes Element im Flussdiagramm eine bedingte ist, die einen anderen Test auf demselben Datensatz durchführt (ohne es zu ändern). Zweige können sich teilen und verschmelzen, aber niemals kreisförmige Weise, dh. Das Flussdiagramm kann nicht wieder auf sich selbst zurückkehren. Bei der Ankunft am Ende einer Niederlassung wird der aktuelle Zustand zurückgegeben und das Programm verlässt.

Ein typisches Programm ähnelt oberflächlich einem Programm in einer rein funktionalen Sprache, außer dass keine Rekursionsform zulässig ist und Funktionen niemals etwas zurückgeben können. Die einzige Möglichkeit, eine Funktion zu beenden, besteht darin, eine andere Funktion aufzurufen oder eine allgemeine Exit -Anweisung aufzurufen, die den aktuellen Zustand zurückgibt. Ein ähnlicher Effekt könnte auch erreicht werden, indem eine strukturierte Programmiersprache und die Entfernung aller Schleifenanweisungen oder eine "unstrukturierte" Programmiersprache entfernen und jede GOTO- oder JMP -Anweisung verbieten, die im Code rückwärts geht.

Jetzt ist meine Frage: Gibt es eine kurze und genaue Möglichkeit, eine solche Sprache zu beschreiben? Ich habe keinen formalen CS -Hintergrund und es fällt mir schwer, Artikel über Automatentheorie und formale Sprachtheorie zu verstehen, also bin ich ein bisschen ratlos. Ich weiß, dass meine Sprache nicht vollständig ist, und durch große Schmerzen konnte ich mir versichern, dass meine Sprache wahrscheinlich Kann als "reguläre Sprache" klassifiziert werden (dh eine Sprache, die durch eine schreibgeschützte Turing-Maschine bewertet werden kann), aber gibt es einen spezifischeren Begriff?

Bonuspunkte, wenn der Begriff für ein Publikum, das in allgemeinen Programmierkonzepten vertraut ist, intuitiv verständlich ist, aber keinen formalen CS-Hintergrund hat. Auch Bonuspunkte, wenn es eine bestimmte Art von Maschine oder Automat gibt, die eine solche Sprache bewertet. Oh ja, denken Sie daran, dass wir einen Datenstrom nicht bewerten - jedes Element hat (schreibgeschützte) Zugriff auf den vollständigen Satz von Eingabedaten. :)

Answer 1

Ich weiß, dass diese Frage etwas alt ist, aber für die Nachwelt ist der Satz, den Sie suchen, "Entscheidungsbaum". Sehen http://en.wikipedia.org/wiki/decision_tree_model für Details. Ich glaube, das erfasst genau das, was Sie getan haben, und hat einen ziemlich beschreibenden Namen!

Answer 2

Ich glaube, dass Ihre Sprache ausreichend mächtig ist, um genau die zu kodieren sternfreie Sprachen. Dies ist eine Untergruppe dieser regulären Sprachen, in der kein Ausdruck einen Kleene -Stern enthält. Mit anderen Worten, es ist die Sprache der leeren Zeichenfolge, des Nullsatzes und der einzelnen Zeichen, die unter Verkettung und Disjunktion geschlossen sind. Dies entspricht der Reihe von Sprachen, die von DFAs akzeptiert werden und keine gerichteten Zyklen enthalten.

Ich kann hier angesichts Ihrer Beschreibung Ihrer Sprache einen Beweis dafür versuchen, obwohl ich nicht sicher bin, ob es genau richtig funktioniert, da ich keinen vollen Zugriff auf Ihre Sprache habe. Die Annahmen, die ich mache, sind wie folgt:

1. Keine Funktionen sind jemals zurückgekehrt. Sobald eine Funktion aufgerufen wird, wird sie niemals den Steuerfluss an den Anrufer zurückgeben.
2. Alle Aufrufe werden statisch aufgelöst (dh Sie können den Quellcode betrachten und einen Diagramm jeder Funktion und den Satz von Funktionen erstellen, den es aufruft). Mit anderen Worten, es gibt keine Funktionszeiger.
3. Die Anrufdiagramm ist acyclisch; Für die Funktionen A und B gilt genau einer der folgenden Funktionen: A ruft transitiv B, B transitiv A oder weder A noch B transitiv auf.
4. Allgemeiner ist das Kontrollflussdiagramm acyclisch. Sobald ein Ausdruck bewertet wird, wird nie wieder ausgewertet. Dies ermöglicht es uns, das Obige zu verallgemeinern, damit wir uns das Programm als eine Reihe von Aussagen als DAG bezeichnen können, anstatt an Funktionen zu denken, die andere Funktionen bezeichnen.
5. Ihre Eingabe ist eine Zeichenfolge, in der jeder Buchstaben einmal und nur einmal gescannt wird und in der Reihenfolge, in der er angegeben ist (was angesichts der Tatsache, dass Sie versuchen, Flow -Diagramme zu modellieren, vernünftig erscheint).

Angesichts dieser Annahmen ist hier ein Beweis dafür, dass Ihre Programme eine Sprache akzeptieren, wenn die Sprache sternfrei ist.

Um zu beweisen, dass wenn es eine sternfreie Sprache gibt, befindet sich in Ihrer Sprache ein Programm, das es akzeptiert, damit die DFA für diese Sprache mit dem Mindestzustand erstellt wird. Sternfreie Sprachen sind schleifefrei und scannen die Eingabe genau einmal. Daher sollte es einfach sein, ein Programm in Ihrer Sprache aus der DFA zu erstellen. Insbesondere bei einem Staat s Mit einer Reihe von Übergängen zu anderen Zuständen, die auf dem nächsten Symbol der Eingabe basieren, können Sie eine Funktion schreiben, die sich mit dem nächsten Zeichen der Eingabe befasst und dann die Funktion aufruft, die den übergeführten Zustand codiert. Da die DFA keine gerichteten Zyklen hat, haben die Funktionsaufrufe keine gerichteten Zyklen, so dass jede Anweisung genau einmal ausgeführt wird. Wir haben jetzt das (∀ R. ist eine sternfreie Sprache → ∃ Ein Programm in Ihrer Sprache, das es akzeptiert).

Um die umgekehrte Implikationsrichtung zu beweisen, kehren wir diese Konstruktion im Wesentlichen um und erstellen eine ε-NFA ohne Zyklen, die Ihrem Programm entspricht. Wenn Sie eine Untergruppe auf dieser NFA durchführen, um sie auf eine DFA zu reduzieren, werden keine Zyklen eingeführt. Sie haben daher eine sternfreie Sprache. Die Konstruktion ist wie folgt: Für jede Aussage s s_ich Erstellen Sie in Ihrem Programm ein Status Q_ich Mit einem Übergang zu jedem der Staaten, die den anderen Aussagen in Ihrem Programm entsprechen, die nur einen Sprung von dieser Aussage entfernt sind. Die Übergänge zu diesen Zuständen werden mit den Symbolen des verbrauchten Eingaben gekennzeichnet, die jede der Entscheidungen treffen, oder ε, wenn der Übergang ohne Eingabe auftritt. Dies zeigt, dass (∀ Programme P in Ihrer Sprache und existiert; eine sternfreie Sprache, die nur die von Ihrer Sprache akzeptierten Saiten akzeptiert).

Zusammengenommen zeigt dies, dass Ihre Programme identisch die Kraft der sternfreien Sprachen haben.

Natürlich könnten die Annahmen, die ich über das gemacht habe, was Ihre Programme tun können, zu begrenzt sein. Möglicherweise haben Sie zufällige Zugang zur Eingabesequenz, die ich denken kann mit einer Modifikation der obigen Konstruktion behandelt werden. Wenn Sie möglicherweise Zyklen in der Ausführung haben, bricht diese ganze Konstruktion. Aber selbst wenn ich mich irre, hatte ich immer noch viel Spaß daran, darüber nachzudenken, und danke Ihnen für einen angenehmen Abend. :-)

Hoffe das hilft!