regex - 如何将正则表达式转换为有限自动机？

Question

如何将以下正则表达式更改为有限自动机？

(abUb)(bUaaa)b*b((a*b)*Ub)*

注意：在这种情况下，U 表示联合

Answer 1

此正则表达式有五个顶级级联组件。根据可从 Kleene 定理的一部分中恢复的算法，您可以为这些创建 NFA-Lambda，然后通过将一个的最终状态连接到下一个的初始状态来形成连接。

当你看到一个联合时，这意味着你制造了两台机器，并通过使用两个 lambda 转换创建一个新的开始状态来组合它们。

Kleene 闭包涉及更多一点，但基本上是为重复的事物制造机器，然后通过添加新的接受开始状态和从旧的最终状态到它的循环来对其进行转换。

基本情况是单个字母的机器，它有两种状态，初始和最终，带有适当标记的转换。

从最简单的机器（最里面的子表达式）到整个事物递归地工作，并根据需要进行组合。尽可能简化结果，可能转换为最小 DFA。

Answer 2

有一个名为 Automatic Java Code Generator for Regular Expressions and Finite Automata 的应用程序，它可以为给定的正则表达式或有限自动机自动生成 NFA、DFA（包括转换表）和 Java 代码。可以从这个链接下载：www.s-solutions.info您可以随时检查您的解决方案是否正确。