问题标签 [automata-theory]

对于使用正则表达式或（显然等效的）确定性有限自动机很容易的情况，我无法为 NFA 制作接受状态。

例如，如果机器只在最后没有任何状态可能的情况下接受怎么办？您可以使用 powerset 构造来制作接受状态为空集的 DFA。我能想到用 NFA 做到这一点的唯一方法是让每个状态都“接受”，然后在最后翻转它，所以接受实际上是失败的。

更糟糕的是，如果您有 6 个状态并想要检查，例如，您是否可能处于所有状态 {0,1,2}，但绝对不在{3,4,5} 中，该怎么办？同样，这对 DFA 来说很容易。

有没有一种简单的方法可以针对这些情况调整 NFA？

谢谢！

你好我想问你这个问题。

我应该（手动）计算格雷巴赫范式中的语法，生成语言

L = {ai bj ck | i + j = 2k and k >= 1}

我真的不知道。有人可以帮帮我吗？

提前
谢谢克里斯

我一直在练习一些关于自动机理论的问题，在那里我遇到了一个关于最小 dfa 的问题，我无法弄清楚我哪里出错了。我在最小 dfa 中得到了 4 个状态，但我的书说答案是 3。问题要求给定的 NFA 转换为最小 DFA 并计算后一个中的状态数。给定的 NFA（p 和 r 分别是初始状态和最终状态）是：

我得到 4 个状态：[r]、[p]、[q,s]、[dead]。最终的 [r] 和非最终状态 [q,s] 可以在这里合并，因为它们会导致相似接收输入 a 和 b 的配置？？我了解到最终和非最终状态不能在同一个等价类中......

我们都知道这(a + b)*是一种只包含符号a和的常规语言b。但是(a + b)*是一个无限长的字符串，它是有规律的，因为我们可以构建一个有限自动机，所以它应该是有限的。

谁能解释一下？

找到接受给定语法的相同语言的正则表达式的过程步骤是什么？

• S --> b | AA
• 一个--> aA | 艾伯 | ε

令 L = {一个ⁿ | n >= 0}，其中所有n >= 1。

因此 L 由所有长度的 a 序列组成，包括长度为 0 的序列。设 L2 是 L 的任何无限子集。我需要证明总是存在一个 DFA 来识别 (L2)*。

如果 L2 是有限子集，则非常明显，因为 L2 将是 DFA，因此通过克莱恩闭包，L2* 将被 DFA 识别。但是我无法为无限子集得到它，因为 L2 可能不会表示为 DFA，例如字符串的长度是素数。

这是一个模棱两可的CFG：

您可以通过解析字符串“ba”轻松检查语法的歧义。

是否有任何算法可以解决上述 CFG 的歧义？

谢谢您的帮助

SCXML 的局限性是否与确定性有限自动机/确定性有限状态机相同，或者 SCXML 的功能是否可以更好地被其他抽象机器/自动机捕获？例如，SCXML 能否被认为足以描述下推自动机或图灵机？

在构造确定性下推自动机时，每个状态都可以是最终状态吗？

我在构建一个接受以下语言的 DPDA 时遇到了麻烦：

L = { 0 ⁿ 1 ^m | n ≥ m }

我的方法是使初始状态成为最终状态，可以将 0 推入堆栈以获取输入 0，然后转换到另一个最终状态，该最终状态可以从堆栈中弹出 0 以获取输入 1。我相信这个解决方案是正确的，但是每个状态都是最终状态似乎不寻常，我想验证我的方法是否有效。

这是正确的方法吗？我可以将两种状态都作为最终状态吗？这是我的 DPDA 的确切转换函数 δ。

δ(q ₀ , 0, Z ₀ ) = { (q ₀ , 0 Z ₀ ) }

δ(q ₀ , 0, 0) = { (q ₀ , 0 0) }

δ(q ₀ , 1, 0) = { (q ₁ , ε) }

δ(q ₁ , 1, 0) = { (q ₁ , ε) }

我需要了解这个 DFA 吗？我没看懂，尤其是图中的三个点。我对为什么过渡指向它指向的位置有一个模糊的想法。但我仍然很困惑。因此，如果有人能说出这些点的含义，那就太好了：

1. 当它们出现在过渡名称上时，例如 1？2. 什么时候出现在两个不相连的状态之间？