是否有一种只具有确定性下推自动机功能的编程语言,而不是更多？

Question

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

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

1. 具有将值推入堆栈并将值从堆栈中弹出的操作的堆栈.

2. 有限状态机(FSM)用于输入值,从状态移动到状态,与堆栈交互以及输出结果.

我意识到我可以使用Java或C或Python(等)并通过编写仅使用堆栈和FSM的程序来约束语言.但是,我正在寻找一种只具备这些功能的编程语言,而不是更多.

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

Answer 1

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

然而，这不是问题：您无需担心使用过多的电量。机器语言是典型的高效语言（开销最小！），它是图灵完备的，这表明效率与理论能力并不紧密相关。