问题标签 [nfa]

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

谢谢。

我一直想知道输入锚 ( ^) 的开头是如何转换为 flex 中的 FSA 的。我知道行尾锚 ( $) 与要匹配r/\n的r表达式匹配。输入锚的开头如何匹配？我看到的唯一解决方案是使用开始条件。它如何在程序中实现？

我正在尝试编写一个程序，该程序将接受描述正则表达式的字符串。例如：

其中 U 是联合运算符， * 是 Kleene 星（我们还看到了隐含的串联）。

我考虑过标记字符串的原子并基于运算符和操作数构建机器。我想用类似于这样的规则对每个原子进行算法操作：http ://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

我不确定如何以智能方式最好地解析这种类型的输入，以便我可以以编程方式构建 NFA。

我的程序的目标是接受上述输入并输出将由其 5-touple 描述的相应 NFA。非常感谢任何有关实现该目标的建议。

我是 Prolog 的初学者，我想问一个关于 Prolog 的问题。

我的程序基于非确定性有限状态自动机。

起始状态为S0，最终状态为S3。

图是

所以如果有一个字符串[a,a,b,b,c,c]它应该像

有一个谓词accepts(Ls)if（有Ls一个字符串列表）

并假设 NFA 从状态Si到状态Sj并且在它们之间存在状态Sk，goesTo谓词定义为

但是，如果查询（从到的accepts(Ls)任意字符串列表），教程问题说它几乎肯定会进入无限搜索并且会发生堆栈溢出。ac

但是，我不明白为什么查询会进入无限搜索并导致堆栈溢出。如果你能给我一个理由，那就太好了！

（编辑：）确切的报价是：

“一个典型的 Prolog 用户可能希望他/她的 goTo 规则是这样的，即查询接受（X）会生成被上述 NFA 接受的连续字符串。几乎可以肯定，鉴于给定 NFA 的上述表示，Prolog 系统将进入无限搜索并发生堆栈溢出。说明为什么会这样。（如果您要避免此问题，请说明您如何设法避免它）。

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

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

要求：

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

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

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

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

我已经找到：

在 Stream 上应用正则表达式？

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

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

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

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

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

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

什么是绘制最小的直接和简单的方法DFA，它接受与给定相同的语言Regular Expression(RE)。
我知道可以通过以下方式完成：

但是有什么捷径吗？像(a+b)*ab

我正在为明天的考试而学习，我已经检查了许多教程，告诉我如何将 NFA 转换为正则表达式，但我似乎无法确认我的答案。按照教程，我解决了 NFA

我的解决方案是：

阿坝_

我对么？

使用pumping lemma，我们可以很容易地证明该语言L1 = {WcW^R|W ∈ {a,b}*}是正则语言。（字母表是{a,b,c}；W^R 代表逆向字符串W）

但是，如果我们用 替换字符c，"x"(x ∈ {a,b}+)比如说L2 = {WxW^R| x, W ∈ {a,b}^+}，，那么 L2是一种常规语言。

你能给我一些想法吗？

众所周知，使用抽引引理，我们可以很容易地证明语言L = {WW|W ∈ {a,b}*}不是正则语言。

然而，语言，L1 = {W1W2| |W1| = |W2|} 是一种常规语言。因为我们可以像下面这样得到 DFA，

我的问题是，L = {WW|W ∈ {a,b}*}也有偶数长度的字符串（|w|=|w|，绝对），L 仍然可以有一些像上面那样的 dfa。怎么不是普通语言？

谢谢。