Gibt es eine Programmiersprache, die nur die Macht eines deterministischen Push-Down-Automaten hat, und nicht mehr? - Stack, Finite-State-Maschine, deterministisch, Turing-Komplett, Pushdown-Automat

Einige Programmierprobleme erfordern nicht die volle Leistung einer Turing-Maschine, um sie zu lösen. Sie können mit viel weniger Leistung gelöst werden.

Gibt es eine Programmiersprache auf hoher Ebene, die nur diese Funktionen unterstützt:

1. Ein Stapel mit Operationen, um Werte auf den Stapel zu schieben und Werte aus dem Stapel zu ziehen.

2. Eine Finite-State-Machine (FSM), um Werte einzugeben, von Zustand zu Zustand zu wechseln, mit dem Stapel zu interagieren und Ergebnisse auszugeben.

Mir ist klar, dass ich Java, C oder Python verwenden könnte(etc.) und beschränken Sie die Sprache, indem Sie ein Programm schreiben, das nur einen Stack und einen FSM verwendet. Ich suche jedoch eine Programmiersprache, die nur über diese Fähigkeiten verfügt und nicht mehr.

Mit anderen Worten, ich möchte keine verwendenTuring-komplette Programmiersprache zur Lösung von Problemen, für die nur deterministische Push-Down-Automaten erforderlich sind. Ich möchte eine Programmiersprache verwenden, die nur über deterministische Pushdown-Automaten verfügt.

Antworten:

Kurz gesagt, Sie werden kein hohes Niveau findenSprache mit dieser kleinen Kraft. Dies ist nicht unbedingt eine Definition, aber eine hohe Ebene impliziert eine gewisse Abstraktion, die der Komplexität entspricht.

Dies ist jedoch kein Thema: Sie brauchen sich keine Sorgen zu machen, zu viel Energie zu verwenden. Maschinensprache, die kanonisch effiziente Sprache (minimaler Aufwand!), ist Turing vollständig, was darauf hinweist, dass Effizienz nicht an theoretische Leistung gebunden ist.

Ich bin nicht sicher, ob dies zählt, aber der LR (1)Grammatiken erfassen genau die Macht deterministischer PDAs - wenn es für eine Sprache eine LR (1) - Grammatik gibt, gibt es einen deterministischen PDA und umgekehrt. Wenn Sie sich Tools wie yacc oder bison anschauen, sie so einstellen, dass sie LR (1) - Grammatiken verwenden, und semantische Aktionen mit beliebigem Code nicht zulassen, könnten Sie argumentieren, dass Sie eine Programmierumgebung mit genau der Leistungsfähigkeit hinterlassen von einem deterministischen PDA. Zugegeben, es ist ein bisschen eine Strecke. :-)

Hoffe das hilft!