2

我创建了一种特殊用途的“编程语言”，故意（通过设计）不能两次评估同一段代码（即它不能循环）。它本质上是用来描述一个类似流程图的过程，其中流程图中的每个元素都是一个条件，它对同一组数据执行不同的测试（不能修改它）。分支可以拆分和合并，但不能以循环方式，即。流程图不能循环回到自身。当到达分支结束时，返回当前状态并退出程序。

写下来时，典型的程序在表面上类似于纯函数式语言的程序，除了不允许任何形式的递归并且函数永远不能返回任何内容。退出函数的唯一方法是调用另一个函数，或者调用返回当前状态的通用退出语句。通过采用结构化编程语言并删除所有循环语句，或者通过采用“非结构化”编程语言并禁止在代码中倒退的任何 goto 或 jmp 语句，也可以实现类似的效果。

现在我的问题是：有没有一种简洁准确的方式来描述这种语言？我没有任何正式的CS背景，对于自动机理论和形式语言理论的文章我很难看懂，所以我有点不知所措。我知道我的语言不是图灵完备的，经过巨大的痛苦，我设法向自己保证，我的语言可能可以归类为“常规语言”（即可以由只读图灵机评估的语言），但有更具体的术语吗？

如果该术语对于精通一般编程概念但没有正式 CS 背景的观众可以直观地理解，则可以加分。如果有一种特定类型的机器或自动机可以评估这种语言，也可以加分。哦，是的，请记住，我们不是在评估数据流 - 每个元素都可以（只读）访问完整的输入数据集。:)

4

2 回答 2

1

我相信您的语言足够强大，可以精确地编码无星号语言。这是常规语言的一个子集，其中没有表达式包含 Kleene 星。换句话说，空字符串、空集和单个字符的语言在连接和析取下是封闭的。这相当于 DFA 接受的一组语言，其中没有任何有向循环。

鉴于您对您的语言的描述，我可以在这里尝试证明这一点，但我不确定它是否能正确工作，因为我没有完全访问您的语言的权限。我所做的假设如下：

  1. 没有函数返回。一旦一个函数被调用，它永远不会将控制流返回给调用者。
  2. 所有调用都是静态解析的（也就是说，您可以查看源代码并构建每个函数及其调用的函数集的图）。换句话说，没有任何函数指针。
  3. 调用图是非循环的；对于任何函数 A 和 B，则恰好满足以下条件之一：A 传递调用 B，B 传递调用 A，或者 A 和 B 都不传递调用另一个。
  4. 更一般地，控制流图是非循环的。一旦表达式求值，它就不再求值。这使我们可以概括上述内容，以便我们可以将程序视为一系列语句，这些语句都作为 DAG 相互调用，而不是考虑调用其他函数的函数。
  5. 您的输入是一个字符串，其中每个字母仅被扫描一次，并且按照给出的顺序（考虑到您正在尝试对流程图建模，这似乎是合理的）。

鉴于这些假设，这里有一个证据表明您的程序接受一种语言，如果该语言是无星的。

To prove that if there's a star-free language, there's a program in your language that accepts it, begin by constructing the minimum-state DFA for that language. Star-free languages are loop-free and scan the input exactly once, and so it should be easy to build a program in your language from the DFA. In particular, given a state s with a set of transitions to other states based on the next symbol of input, you can write a function that looks at the next character of input and then calls the function encoding the state being transitioned to. Since the DFA has no directed cycles, the function calls have no directed cycles, and so each statement will be executed exactly once. We now have that (∀ R. is a star-free language → ∃ a program in your language that accepts it).

为了证明蕴涵的相反方向，我们基本上颠倒了这个结构，并创建了一个没有环的 ε-NFA 与您的程序相对应。对此 NFA 进行子集构造以将其简化为 DFA 不会引入任何循环，因此您将拥有无星号语言。构造如下：为程序中的每个语句 s i创建一个状态 q i with a transition to each of the states corresponding to the other statements in your program that are one hop away from that statement. The transitions to those states will be labeled with the symbols of input consumed making each of the decisions, or ε if the transition occurs without consuming any input. This shows that (∀ programs P in your language, &exists; a star-free language R the accepts just the strings accepted by your language).

Taken together, this shows that your programs have identically the power of the star-free languages.

Of course, the assumptions I made on what your programs can do might be too limited. You might have random-access to the input sequence, which I think can be handled with a modification of the above construction. If you can potentially have cycles in execution, then this whole construction breaks. But, even if I'm wrong, I still had a lot of fun thinking about this, and thank you for an enjoyable evening. :-)

Hope this helps!

于 2011-02-01T05:37:12.283 回答
0

I know this question is somewhat old, but for posterity, the phrase you are looking for is "decision tree". See http://en.wikipedia.org/wiki/Decision_tree_model for details. I believe this captures exactly what you have done and has a pretty descriptive name to boot!

于 2011-02-10T19:51:08.777 回答