构建一个 DFA 接受带有联合的语言

Question

我正在尝试弄清楚如何构建接受语言 且字母表为 ∑ = {a, b} 的 DFA。这是家庭作业问题集的一部分，我想我对如何构建简单的 DFA 有一个非常基本的想法，但我无法理解联合符号，更重要的是 u 的意义是什么？

Answer 1

u表示包含as和b[=20=的任意长度（包括0）的字符串]s 以任何顺序。这就是条件 u 是 ∑* 的一个元素的意思。

在一般情况下，您可以通过构建一个 NFA 来构建一个 DFA，该 NFA 的起始状态有多个输出转换，然后对 NFA 执行 ε-闭包。在这种情况下，两个开始转换是互斥的，因此您可以只加入两个 DFA 的开始状态。

这可能在您的教科书 and/or 讲义中有更好的解释。