regex - 我如何构建这个有限自动机？

Question

我正在为离散数学考试而学习，我发现了这个我无法理解的练习。

“为字母表中的语言建立一个基本的有限自动机(DFA，NFA，NFA-lambda)Sigma = {0,1,2}其中字符串中元素的总和是偶数并且这个总和大于3"

我曾尝试使用 Kleene 定理连接两种语言，例如连接与此正则表达式关联的语言:

(00 U 11 U 22 U 02 U 20)* - 偶数元素

这个

(22 U 1111 U 222 U 2222)* - 和大于3的

这有什么意义吗？我认为我的正则表达式很松弛。

Answer 1

我发现你的符号有点模糊，所以我可能完全误解了。如果是这样，请忽略以下内容。看来你还没到:

• 我假设 * 表示“0 次或更多次”。但是，总和 >= 3 的字符串之一必须出现。据说您需要 +(“1 次或多次”)。
• 总和 >= 3 的字符串列表中缺少 112 和 211。
• 该列表中的 222 和 2222 是多余的。
• 所有这些字符串都可以任意穿插 0。
• 00 的和不大于 0 的和。

---

编辑这个怎么样(acc 是唯一的接受状态，dot-source ):

automaton http://student.science.uva.nl/~sschroev/so/885411.png

在 a 和 c 状态下，字符串和总是奇数。在 start、b 和 acc 状态下，和总是偶数。此外，在 start 处总和为 0，在 b 处总和为 2，在 d 处总和 >= 4。这很容易证明.因此，接受状态 acc 满足所有条件。

编辑 2:我会说这是一个接受请求语言的正则表达式:

0*(2|(1(0|2)*1))(0*(2|(1(0|2)*1))+