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

Question

我正在为离散数学考试而学习，但我发现了这个我无法弄清楚的练习。

“为字母 Sigma = {0,1,2} 中的语言构建一个基本的有限自动机 (DFA,NFA,NFA-lambda)，其中字符串中元素的总和是偶数并且这个总和大于 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是唯一的接受状态，点源）：

自动机 http://student.science.uva.nl/~sschroev/so/885411.png

在状态a和c处，字符串总和总是奇数。在状态start，b和acc总和总是偶数。此外，在开始时和为 0，在b处为 2，在d处 >= 4。这可以很容易地证明。因此，接受状态acc符合所有标准。

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

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

Answer 2

不确定这是否回答了您的问题，但是：您需要提交正则表达式吗？或者FSM会这样做吗？

无论如何，首先绘制 FSM 可能会有所帮助，我认为这是一个正确的 DFA：

FSM http://img254.imageshack.us/img254/5324/fsm.png

如果是这种情况，在构造正则表达式时（记住，它的语法与编程“正则表达式”不同）：

0*表示“0 任意多次”。这是有道理的，因为字符串中的 0 不会改变机器的状态。（看，在 FSM 中，0 只是循环回到自身）

您需要考虑“112”或“22”等的不同组合 - 直到您的总和至少达到 4。

如果您的总和大于 3，甚至大于 3，那么 (0|2)* 将使您处于最终状态。否则（总和 > 3，奇数）你需要像 1(0|2)* 这样的东西才能让你处于接受状态。

（不知道这是否有帮助，或者是否正确 - 但这可能是一个开始！）

Answer 3

在 Stephan 的指导下，每个表达式可能是：

(0*U 2* U 11)* - 偶数和

有了这个

(22 U 11 U 222 U 112 U 211 U 121)+ - 总和大于 3

我不知道它是否可以进一步简化，这将有助于设计自动机。

Answer 4

我发现从状态的角度来思考更容易。使用五种状态：0、1、2、EVEN、ODD

过渡：

State, Input -> New State

(0, 0) -> 0
(0, 1) -> 1
(0, 2) -> 2

(1, 0) -> 1
(1, 1) -> 2
(1, 2) -> ODD

(2, 0) -> 2
(2, 1) -> ODD
(2, 2) -> EVEN

(ODD, 0) -> ODD
(ODD, 1) -> EVEN
(ODD, 2) -> ODD

(EVEN, 0) -> EVEN
(EVEN, 1) -> ODD
(EVEN, 2) -> EVEN

只有 EVEN 是接受状态。