Java 中的 NFA 模拟

Question

我被分配了一个任务，需要用Java模拟NFA。现在我需要模拟以下正则表达式的NFA：

ab*((b|d)|c*)

我觉得我有太多的电子符号。我想知道下面的图片是否正确。

- unleashed

---

尽管从这个例子http://t2.gstatic.com/images?q=tbn:ANd9GcRaijg4c8db5s7sQkjlmL_rRCynJE5vx_ZyWFInHPIKELeoq216sA 看来，在我的情况下，从2-3到e似乎存在一个e转换。我知道它可以被简化，但这是正确的做法吗？从（编译器-原理、工具和技术第二版）书中，它展示了类似于提供的链接的例子。 - unleashed

如果那是一个正确的例子，我会说你需要添加一些e转换。 1-a-2-e-3-b-4-e-5... 由于您的跳跃显然无法在一行上完成:P - Brandon Buck

1-a-2-e-3-b-4-e-5？所以我需要添加更多的e转换吗？ - unleashed

@unleashed 你提供的例子是 a*，它是 1-e-2-a-3-e-4（带有跳转）。我只是想指出，如果这是你的教授（或其他人）要求的正确方式，那么你应该将同样的模式应用于代表 b* 的图形部分。 - Brandon Buck

给定的NFA是正则表达式的简单转换。有简单的算法来确定和最小化有限自动机；在任何基本的TCS教科书中都可以找到它们。因此，这个问题可能非常适合即将到来的计算机科学Stack Exchange。所以，如果你想有一个像这样的问题的地方，请继续帮助这个提案起飞！ - Raphael

Answer 1

你的NFA图是正确的。它将匹配正则表达式ab*((b|d)|c*)，但不会匹配其他任何内容。但是，它可能会更简单，例如：

- Staffan Nöteberg

---

我认为这不是完全正确的，分支部分((b|d)|c*)只有两个分支，而不是三个。它要么是(b|d)，要么是c*，所以从你的b节点来看，更准确的表示方式不是将其表示为完全独立的路径，然后分成b或d吗？ - Brandon Buck

我确定上面的那个没有使用汤普森构造法。虽然它更短，但是我的讲师给了我如何完成它的风格。 - unleashed

@unleashed 我认为Thompson是一种用于创建NFA的算法（过程），而不是NFA的一种类型。你可以将我的NFA视为使用Thompson创建并进行优化的内容。（顺便说一句：问题是关于你的NFA是否等价于你的正则表达式，与Thompson无关） - Staffan Nöteberg

@izuriel (b|d)|c* 在正则表达式代数中等同于 b|d|(c*)，是吗？Kleene闭包比Alternation的优先级更高。 - Staffan Nöteberg

@StaffanNöteberg 是的，我理解你的观点。一开始它让我有点困惑，但它们产生的结果是相同的 :P - Brandon Buck