问题标签 [nfa]

我不知道这个问题问得对不对，但我绝对觉得应该问。当然，我确实看到了很多关于互联网和 StackOverflow 本身的很好且内容丰富的问题​​、文章。但是我发现所有的问题或文章都遵循特定的规则或模式来解释该主题。我的意思是，当提出关于 NFA、DFA 或正则表达式的问题时，会针对这些主题的定理/规则（计算理论）提出解决方案。

哪里有艺术，我觉得哪里有直觉。如果这些问题涉及“设计”某些东西，那么每个人都必须有自己的方式（当然不会脱离定理或规则本身）来解决或解决这些问题。人们应该已经开发出一种思考过程（经过多年的实践）来解决这些问题。

我想用一个简单的例子来详细说明这个问题。

考虑问题：

或者

（问题来自 Sipser 的书，我自己也找到了解决方案）

我只想知道，如何培养解决问题的直觉。

我问这个问题是为了培养所有在解决这些问题时遇到困难的初学者（像我一样）的技能和思维过程，即使他们（包括我）对这些主题有足够的理论知识。

任何“建设性”的答案都非常受欢迎！！谢谢你。

当您阅读诸如Regex: NFA 和 Thompson 算法之类的帖子时，一切看起来都相当简单，直到您意识到在现实生活中您不仅需要像“7”或“b”这样的直接字符，而且还需要：

即字符类（或范围）。因此我的问题是——如何使用字符范围构建 NFA？使用诸如“不是 A”、“其他任何东西”之类的元字符，然后计算重叠范围？这将导致在使用最终自动机时使用树状结构，而不仅仅是一个表。

更新：请假设大小 (>>256) 字母不平凡。

我问的是 NFA，但后来我也想将 NFA 转换为 DFA。

我被困在字母表上为给定语言编写正则表达式{a,b}。如果字符串以子字符串 'aa' 开头或以子字符串 'bb' 结尾，则接受这些字符串。

例如{aab, abb, aaba}被接受但{Λ, ab, abaa}不接受。

我尝试的解决方案是：{aa* + ab* + bb*}，但我在想：如果字符串以b怎么办？那我的表情就不行了。。

任何帮助都会很棒！

一点背景知识：我正在实现一个正则表达式匹配引擎（NFA），它应该支持 PCRE 兼容模式（我的意思是它应该捕获具有与 PCRE 相同的偏移量的子表达式）。

PCRE 的 testinput1 中有一个测试，我无法完全理解。它测试惰性量词。

所以，正则表达式是

字符串是

PCRE的比赛是：

它显然是在使用惰性量词。

据我了解，在完全不可能使用另一种“贪婪”方式之前，不应使用惰性量词。现在这是一个可能的贪婪匹配：

它使用条件子模式的负分支，没有惰性量词。

所以我正在寻找这个 PCRE 行为的解释或任何细节/建议，为什么惰性量词在这个测试中匹配。谢谢！

编辑：我还检查了TRE库是如何工作的。这是一个与 POSIX 兼容的 NFA 引擎。我稍微修改了原始的正则表达式以适应 TRE 的语法：

并且输出（使用长度而不是结束偏移）是：

所以关于 PCRE 的回溯特定行为的建议很可能是错误的......

我有一个关于正则表达式的相当基本的问题。
我使用表达式.*而不考虑它匹配期望匹配例如到行尾。这行得通。
但出于某种原因，我开始思考这个表达方式。检查维基百科（我的重点）

所以现在根据这个定义，为什么不.*尝试匹配字符串中的第一个字符 0 次或更多次，而是尝试将匹配应用于字符串中的每个字符？
我的意思是如果我有abc它应该尝试匹配a,aa,aaa etc对吗？
但它没有：

我正在尝试理解以下正则表达式：
具有：

作为多行文本，以下正则表达式无法匹配：

但我不确定为什么。
我的意思是.*将匹配到行尾（\n）。然后由于.无法匹配行尾，匹配失败。那么既然*是可选的，那么正则表达式引擎不应该回溯并释放\并再次尝试匹配吗？
这似乎不会发生，因为反向引用是空的。
有人可以帮我理解这一点吗？

在 DFA 中，我们可以通过对两个自动机的状态进行叉积并接受在两个初始自动机中都接受的那些状态来计算两个自动机的交集。类似地执行联合。尽管我可以使用 epsilon 转换轻松地在 NFA 中进行联合，但我如何进行它们的交集？

我很困惑如何将 NFA 转换为正则表达式。我有一个 NFA，其中起始状态也是最终状态，我不确定我应该做什么。这是我的 NFA 的样子：

我试图遵循我在网上找到的指南，例如：http: //courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf

按照本网站上的步骤，我将此 NFA 分解为：

从这里我把它进一步分解成这个（我认为对应于第 4 步）

在这一点上，我真的不确定如何进行。在课堂上我们根本没有谈论GNFA，所以我在这一点上特别迷茫。关于我应该如何从这一点开始的任何指示？

我在这里看到的是“至少一个 01，后跟 0 个或多个 0 或 1”。

我是否过度简化了这一点，或者只是偏执地认为表达式看起来比绘制的机器复杂得多？

您是否同意在正则表达式中：

是 a、b 和 c 的任意组合吗？或者你会说 c 总是在 a 和 b 之后。