问题标签 [dfa]

显而易见的选择是耗尽所有可能的输入。我想我做到了。但我不太确定它是否有效，并且我没有违反任何非确定性有限自动机的规则。

我的 NFA 由以下给出：(ab u aab u aba)*下面是我的图表。

我错过了什么吗？

在阅读一本书时，我有这个疑问。

它提到

L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod5 =0} 是常规的 其中 n0(s) = s 中 0 的数量，n1(s) = s 中 1 的数量

此外，它提到

L = {s ∈ (0 + 1)* | d(s) mod 5 =2 和 d(s) mod 7 !=4 } 不规则（甚至不是上下文无关的，但它是递归的）其中 d(s) = s 的十进制值（例如 d(101) = 5)

为什么会这样？是因为 DFA 没有内存来存储（记住）s 的十进制值吗？但在那种情况下，第一种语言怎么会是正规的呢？

我有两个正则表达式（简单示例：“[0-9]+”和“[0123456789]+”）。我想看看它们是否完全匹配相同的输入。是否有用于在 java 中进行此检查的内置函数？如果没有，是否有相对简单的算法来进行检查？谢谢！

我面临的问题是，某个正则表达式实现是基于 DFA 还是 NFA。

我要解决这个问题的出发点是什么。也可以问：我在找什么？基本模式和/或特征是什么？一个好的和解释性的链接或一些比较（即使不直接专用于正则表达式）是非常好的。

我在测试中弄错了这个问题，想知道是否有人可以解释它，显示得出结论所采取的步骤。任何帮助，将不胜感激。

在 L_neq = {0^i1^j | 的 PL 证明中 i < j} 给定一个 m-state DFA，有人选择字符串 0^(m/2)1^(m/2+1)。然后他们选择 y = 0 并表明通过抽水，我们可以到达 L_neq 之外的字符串 0^(m/2+1)1^(m/2+1)。这个证明正确吗？为什么或者为什么不？

此外，如果这个证明是错误的，请写下一个正确的证明。

谢谢

DFA 中接受具有“1”作为右起第 5 个符号的字符串所需的最少状态数是多少？字符串在字母表 {0,1} 上定义。

我一直在努力解决这个问题，但无法提出任何建议。任何指针将不胜感激。

问题是：给定所有只接收偶数长度单词的 DFA 的语言，证明它是否在 P 中。

我考虑过制造一台图灵机，它可以像 BFS/Dijkstra 的算法那样遍历给定的 DFA，以便找到从起始状态到接受状态的所有路径，但不知道如何处理循环？

谢谢！

我试图在不使用解析器的情况下从 CSV 文件中分离一行，我需要做的就是使用 php 根据逗号拆分字符串。如果输入中没有逗号，这本身就相当容易，但事实并非如此。我想忽略用双引号括起来的逗号。

完全无视最后一句话，我决定把问题本身改成如下：

我想根据前面没有双引号或分散的双引号对的逗号来拆分字符串。

例子：

其中 * 是匹配项，而 x 不是。

这是否超出了正则表达式的能力，如果没有，是否有可以处理这种输入的正则表达式？

我一直在思考以下问题，我认为答案是肯定的。

DFA 可接受的常规语言的每个子集是否也是 DFA 可接受的，这是真的吗？

我搜索了谷歌，在许多页面中都给出了最小化 DFA 死状态或陷阱状态被删除。我的问题是，如果某些转换未定义，它怎么可能仍然是 DFA。那你说的人呢？