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

Question

我正在准备离散数学测试，我发现这个练习我无法弄清楚。

“为字母表中的语言构建一个基本的有限自动机（DFA、NFA、NFA-lambda） Sigma = {0,1,2}，其中字符串中元素的总和为偶数且该总和大于 3”

我尝试使用克莱恩定理连接两种语言，例如连接与此正则表达式相关的语言：

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

与这个

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

这有意义吗？？我认为我的正则表达式很不稳定。

Answer 1

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

• 我假设 * 表示“0 次或多次”。但是，必须出现 sum >= 3 的字符串之一。据说您需要一个+（“1 次或多次”）。
• sum >= 3 的字符串列表中缺少 112 和 211。
• 该列表中的 222 和 2222 是多余的。
• 所有这些字符串都可以任意散布 0。
• 00 的和不比 0 的和更偶数。

---

编辑： 这个怎么样 （ACC 是唯一的接受状态， 点源):

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

在各州 A 和 C 字符串和总是奇数。在各州 开始, 乙 和 ACC 总和总是偶数。此外，在 开始 总和为 0，在 乙 它是 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，甚至，然后（0 | 2）*将让你在最终状态。否则（总和> 3，和奇数）你需要像1（0 | 2）*为了让你在接受状态

（不知道这是否会有所帮助，或者如果它的正确的 - 但它可能是一个开始）

Answer 3

每个表达，如Stephan的引导，可以是：

（0 * U 2 * U 11）* - 偶数总和

与此一

（22û11ù222ù112ù211Ù121）+ - 其总和的那些大于3

我不知道这是否可以simplfied更多，这将有助于设计的自动机。

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

只有偶数是接受状态。