stack - 是否有一种编程语言仅具有确定性下推自动机的功能，而仅此而已？

Question

一些编程问题不需要图灵机的全部能力来解决。它们可以用更少的力量解决。我正在寻找一种功能较弱的编程语言。

是否存在仅限于支持以下功能的高级编程语言:

具有将值压入堆栈和从堆栈弹出值的操作的堆栈。

有限状态机 (FSM) 用于输入值、从一个状态移动到另一个状态、与堆栈交互并输出结果。

我意识到我可以使用 Java 或 C 或 Python(等)并通过编写仅使用堆栈和 FSM 的程序来限制语言。但是，我正在寻找一种仅具有这些功能而没有更多功能的编程语言。

换句话说，我不想使用图灵完备的编程语言来解决只需要确定性下推自动机功能的问题。我想使用一种仅具有确定性下推自动机功能的编程语言。

Answer 1

简而言之，您不会找到一种功能如此之少的高级语言。这不是严格意义上的定义，但高级意味着与复杂性相对应的一定数量的抽象。

但是，这不是问题:您无需担心使用过多电量。机器语言，规范高效的语言(最小开销!)是图灵完备的，表明效率与理论能力没有紧密联系。