6

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

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

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

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

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

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

4

2 回答 2

0

我不确定这是否重要,但 LR(1) 语法准确地捕捉到了确定性 PDA 的力量——如果一种语言有 LR(1) 语法,那么它就有一个确定性 PDA,反之亦然。因此,如果您查看 yacc 或 bison 之类的工具,将它们设置为使用 LR(1) 语法,并禁止其中包含任意代码的语义操作,您可能会争辩说,您所剩下的是一个具有精确功能的编程环境确定性PDA。诚然,这有点牵强。:-)

希望这可以帮助!

于 2014-12-17T01:58:50.383 回答
0

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

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

于 2013-06-05T06:53:15.103 回答