问题标签 [dfa]

我有一个关于 DFA 最小化的问题。因此，我使用了众所周知的技术将正则表达式转换为 NFA，然后使用 goto / 闭包算法从中构造 DFA。现在的问题是如何最小化它？我在这里看过有关它的演讲：http ://www.youtube.com/watch?v=T9Z66NF5YRk，但我仍然无法理解这一点。什么是 DFA 最小化？这只是合并相同的状态（在相同字符上进入相同状态的状态）还是不同的东西？

所以，我从以下语法开始：

并最终得到以下 DFA（表示为 JSON）：

那么如何最小化它呢？

更新：

好的，这是我的算法。给定以下 DFA：

这就是我为最小化它所做的事情：

1. 对于每个状态（在我的示例中编号为 0、1、2、3、4），获取标识此类状态的唯一哈希（例如，对于 state0，这将是：from=97,to=97,shift=1，对于 state1，此将是：from=97,to=97,shift=3&from=98,to=98,shift=2 等等...)

2. 比较获得的哈希值，如果我们找到两个相同的哈希值，则将其合并。在我的例子中，state2 hash 为：from=98&shift=4&to=98，state4 hash 为：from=98&shift=4&to=98，它们是相同的，所以我们可以将它们合并到新的 state5 中，之后 DFA 将看起来像这样：

   }

3. 继续这个，直到我们没有任何变化，所以下一步（合并状态 1 和 3）会将 DFA 转换为以下形式：

   }

4. 没有更多相同的状态，这意味着我们完成了。

第二次更新：

好的，给定以下正则表达式： 'a' ('ce')* ('d' | 'xa' | 'AFe')+ | 'b' ('ce')* ('d' | 'xa' | 'AFe')+ 'ce'+ 我有以下 DFA (START -> start state, ["accept"] -> so to说转换到接受状态）：

故事是一样的，我如何最小化它？如果我遵循经典的 Hopcroft 算法来构建所有这些表，确定不可区分的状态，将它们合并在一起等等，那么我将获得包含 15 个状态的 DFA（使用此工具：http ://regexvisualizer.apphb.com/使用这个正则表达式 a(ce) (d|xa|AFe)+|b(ce) (d|xa|AFe)+ce+ 来检查）。以下是使用 Hopcroft 算法缩小后 DFA 的样子：

我想出的算法，在“重新思考” Hopcroft 的算法之后，构建的 DFA 比您在上面看到的要小（对不起图像质量，我不得不一步一步地重新绘制它以了解为什么它更小）：

这就是它的工作原理，关于“状态等价”的决定是基于给定状态（例如“START”）的哈希函数的结果，如果我们从该状态开始，可以构建可以从 DFA 构造的短字符串. 给定上面的 DFA 和 START 状态，我们可以构造以下字符串：98->120, 98->100, 98->65, 98->99, 97->120, 97->100, 97->65 , 97->99 所以让它成为 START 状态的哈希函数的结果。如果我们为 DFA 中的每个状态运行此函数，我们将看到对于某些状态，此函数为我们提供相同的结果（“1.2”、“6.7”、“2.3”和“10”、“13”和“15” ，“16”和“11”，“8”，“26”，“23”和“12”，“9”，“4”，

我看到我在某个地方错了，但不明白我的算法产生的最小化 DFA 有什么问题？

我的语法中的注释块有一些问题。语法很好，但第 3 步 DFA 扫描程序抱怨我的处理方式。

我试图解析的语言如下所示：

{statement}{statement} 等

每个语句中可以包含几种不同类型的注释：

这是一个简化的语法，显示了我遇到的问题：

第 3 步是抱怨 <Statements> 中的 } 和词组末尾的 }。

有人知道如何完成我需要的吗？

[编辑]
我让 REM 部分使用以下内容：

这实际上是理想的，因为备注对我来说不一定是噪音。

仍然有评论词汇组的问题。我会以同样的方式解决问题。

我被要求构建一个 DFA A 和 NFA B，使得 L(D) = L(N) 具有某些特定条件。我不是在寻求解决方案或答案；我只是想确保我有正确的方法来解决这个问题。

首先，我对“构建”这个词有点困惑。他们只是想画一个自动机吗？那会被认为是“建成”吗？

我正在考虑绘制适合该条件的 NFA B。然后使用绘图，我将构造一个等价的 DFA A。在某处有一个定理说等价的自动机具有相同的语言。所以我不需要做任何进一步的事情来显示 L(A) = L(B) 对吗？

谢谢！

我写了一个可以生成 DFA 的程序。但是 DFA 有点不正确。也就是说，有时他们不能接受正确的字符串。

我的问题是：是否有任何算法可以纠正 DFA，以便它们可以接受给定的正确字符串？

更正式地说，

假设 DFA D不接受字符串str。

需要一个算法A , st D' = A( D, str)并且D'接受str

正如标题所示，我希望有人帮助我编写 NFA 到 DFA 的转换。我只需要伪代码。我试过用谷歌搜索，甚至找到了整个源代码，但是几乎没有资源可以帮助我给我一个正式的方法（用书面文字，而不是通过图片）进行转换。这是一道作业题，而且我已经过了截止日期，所以在这里我真的需要一些利他主义。

谢谢。

问题：

定义一个 DFA，它接受 {0,1} 上的所有字符串，这样五个连续位置的每个块都至少包含两个 0。请仔细阅读问题。问问自己：这是否允许 e (epsilon (empty string)) 被接受？0101怎么样？这样的英文描述可以在各种书籍中找到，我想确保您知道如何阅读和解释。

讲师提示：““5 块”DFA 可以通过编程方式轻松生成。我两种方式都可以（手动和编程方式）。因为我擅长 Emacs 和键盘宏，我什至可以手动完成' 机械且相当快。但程序化不太容易出错且紧凑。“

我把这件事画出来了，我认为我做错了，因为它已经失控了。

我在 python 中制作 DFA 之前的草图：

但是，这是不对的，因为索引 2、3、4、5 和 6 构成了一个由五个连续位置组成的块，所以我需要在其中考虑至少两个零。哦，太好了，我一直认为它需要两个 1，而不是两个 0。我会以完全错误的方式解决这个问题吗？因为按照我的想法，这将有大量的状态。

（回到画这个大的 DFA）

同上。Java 或 C# 是最好的，但任何命令式语言都可以。

我正在寻找一种对数据流进行操作的正则表达式匹配的实现——即，它有一个 API，允许用户一次传入一个字符并在字符流上找到匹配项时报告到目前为止看到。只需要非常基本（经典）的正则表达式，因此基于 DFA/NFA 的实现似乎非常适合该问题。

基于可以在单次线性扫描中使用 DFA/NFA 进行正则表达式匹配的事实，似乎应该可以实现流式处理。

要求：

• 在执行匹配之前，库不应尝试等到完整的字符串被读取。我真正拥有的数据是流式传输的；没有办法知道有多少数据会到达，不可能向前或向后搜索。

• 为几个特殊情况实现特定的流匹配不是一种选择，因为我事先不知道用户可能想要寻找什么模式。

• 语言：可从 C/C++ 使用

出于好奇，我的用例如下：我有一个在完整系统模拟器内拦截内存写入的系统，我想有一种方法来识别与正则表达式匹配的内存写入（例如，可以使用它来找到系统中将 URL 写入内存的点）。

我已经找到：

在 Stream 上应用正则表达式？

将正则表达式应用于 Java I/O 流

Code Guru - 使用 .NET Framework 构建正则表达式流搜索

但是所有这些都试图先将流转换为字符串，然后再使用常用的正则表达式库。

我的另一个想法是修改RE2 库，但根据作者的说法，它是围绕整个字符串同时在内存中的假设构建的。

如果没有可用的东西，那么我可以开始重新发明这个轮子以满足我自己的需求的不愉快的道路，但如果我可以避免它，我真的宁愿不这样做。任何帮助将不胜感激！

我需要帮助设计一个接受单词“hello”、“hello world”和“stay together”的 nfa，字母表包括英文字母表、数字和符号。我需要帮助开始。有人有什么建议吗？

例如：给定以下符号序列，

可以接受它的最简单的 DFA 是 17 个状态的链。

而下面的正则表达式可以推导出上面的序列：

对应的最小 DFA 有 8 个状态。

此外，正则表达式的a ((b c)* (d)*)* e最小 DFA 更小，有 4 个状态。它可以接受示例序列。

在上面的例子中，我只考虑了*运算符；更一般地，算子|也可以考虑减小 DFA 的大小。

所以，一般的问题是：

给定一个符号序列，如何找到能够接受它的最小 DFA？