问题标签 [non-deterministic]

如何使用非确定性图灵机显示语言对上下文敏感？

我知道线性绑定自动机（LBA）接受的语言是上下文相关的语言。LBA 是一个非确定性的图灵机。

知道如何将所有这些联系起来并表明一种语言是上下文相关的吗？

我需要实现一个非确定性的 FSM，所以我想出了定义一个 FSM 类的想法，该类包含状态和转换（可能取决于也可能不取决于其他 FSM 的状态，但必须取决于事件/输入）每个对象并将静态 std::map 添加到每个 FSM 将在构造时注册的类。这样，在事件/输入上，每个 FSM 可以在需要时查找其他 FSM 的状态并做出相应的行为，而无需将所有 FSM 组合成一个巨大的确定性 FSM。

这适用于一个 NFSM，这是我现在所需要的，但如果需要更多，可以扩展吗？这种设计有什么根本错误吗？

不太了解 Haskell 中并发和并行上下文中的确定性。一些例子会有所帮助。谢谢

我正在尝试使用 ANTLR（尝试了 3.3 和 3.4）。当我尝试运行我的测试代码时会发生奇怪的事情。请先看我非常简单的代码，之后我会解释我的问题。

测试语法：

测试代码：

编译：

第一个问题是它不打印任何东西:)。我在 Intellij IDEA (10) 工作，我试图从这里运行代码但没有成功（在 CLASSPATH 中使用 ANTLR）。但是，如果我将断点放在int i = 1，调试并等待，比如说 1-3 秒再继续，它就可以了！如果我在没有断点的调试模式下运行它，它不会。有人可以向我解释可能是什么问题吗？谢谢你。

编辑：

所以我试着你放：

紧接着

它奏效了。然而，随后我开始调试CommonTokenStream构造函数（几分钟），当我开始调试时，我得到tokens.fill()了 IndexOutOfBoundException。所以不知何故在后台做了一些事情，但我在 IDEA 中看不到其他线程。

编辑2：

问题解决了。看来有必要先打电话fill()，这BufferedTokenStream可能不应该像这样使用。我遵循了本教程http://bkiers.blogspot.com/2011/03/2-introduction-to-antlr.html它可能对作者有用（我想知道为什么）。IntelliJ IDEA 调试器调用toString()本地对象，然后调用它，fill()这就是我设置断点时它工作的原因。toString()修改状态是邪恶的！

我目前正在编写一个项目，我大量使用了ListTmonad 转换器。使用普通列表时，实现非确定性非常容易。但是，一旦我不得不将我的代码转换为¹ListT，它就会变得更加复杂。

举个简单的例子：从[a]到转换ListT a实际上需要组合两个函数：

虽然它很简单，但我很惊讶它还没有。

问题：

• 有没有更好的方法来处理需要单子变压器的不确定性？
• 是否有任何技术/库可以在列表和列表之间来回转换干净ListT？

¹确切的原因很复杂，所以我真的不想过多阐述。

我在使用 xml 架构时遇到了问题。

首先，我想向您展示 xml 的可能情况：

1.

2.

3.

4.

5.

6.

情况 5 和 6 只有在设置了 Presentee 时才可能。

现在我创建了一个模式来处理这个：

我尝试了对结构的几处更改，以处理问题，但我没有得到“好的”解决方案。

维基百科指出，确定性状态自动化“为每个输入字符串生成自动机的唯一计算（或运行）”。

我一直理解这一点，因为只有 1 种可能的路径来计算任何唯一的字符串。在这种情况下，以下是 DSM。

但是现在我想多了，并将描述解释为每个输入字符串都有一个可能的路径，并且该路径与所有其他输入字符串都是唯一的。在这种情况下，以下不是 DSM，因为“11”和“12”遵循相同的路径。

所以我的问题是，以下是 DSM 还是 NDSM？

相同的数学运算能否在不同的架构或浏览器中返回不同的结果？

我已经走到了尽头：我有一个单线程 C++ 程序。这里是一些经验数据和背景信息，我试图突出最重要的关键词；

• 我正在谈论的整个部分没有任何系统调用，除了标准 C++ 库可能执行的内存（取消）分配调用（std::set涉及 s）。这是一个纯粹的逻辑算法。
• 这个行为应该是确定性的，取决于输入，我不会改变。
• 如果 bug 出现，程序就会陷入看起来像是无限循环的状态，它似乎开始分配超出任何界限的内存。
• 该错误不会以可预测的方式表现出来，我可以从命令行运行程序，有时（可能 30%-50%）该错误会表现出来，否则，据我所知，一切运行顺利且正确。
• 一旦我不是直接从提示符运行程序，而是在gdb 或 valgrind 中运行程序，错误就消失了，程序永远不会死。
• 现在是最好的部分：我将问题追溯到（模板化的）非虚拟成员函数调用。就在通话之前，我向 打印一条消息std::cout，我可以在终端中看到该消息。函数内的第一行还有一条调试消息，它从未显示。

我再也看不到任何合理的解释了。也许你可以想出一个如何进行的想法。

编辑：重要的代码行，我更改了行号，以便我们可以参考它们并省略不相关的部分，因此并非所有内容似乎都是最有意义的。

a.cpp

b.cpp

最后一行输出是：

然后它被困在无限循环中。

malloc不能保证返回 0'ed 内存。传统观点不仅如此，而且内存malloc返回的内容实际上是非确定性的，例如openssl 将它们用于额外的随机性。

然而，据我所知，malloc建立在brk/sbrk之上，它“返回”0'ed内存。我可以看到为什么malloc返回的内容可能是非 0，例如来自以前释放的内存，但为什么它们在“普通”单线程软件中是不确定的？

1. 传统智慧真的是真的吗（假设相同的二进制文件和库）
2. 如果是这样，为什么？

编辑有几个人回答解释了为什么内存可以为非0，我已经在上面的问题中解释过。我要问的是为什么使用 malloc 返回的内容的程序可能是不确定的，即为什么它每次运行时都会有不同的行为（假设相同的二进制文件和库）。非 0 不暗示非确定性行为。换一种说法：为什么每次运行二进制文件时它都有不同的内容。