dfa - 我怎样才能使以下条件的DFA？

Question

请帮我制作以下条件的DFA：

L = { w: n _a (w) mod 3 > n _b (w) mod 3 },

其中 n _a (w) 表示ain w 的出现次数，n _b (w) 表示bin w 的出现次数。

Answer 1

首先为 n(a)mod3 水平设计 DFA，并将其初始状态设计为垂直 n(b)mod3 .....总共需要 9 个状态并标记状态 (a,b)，其中 a 是 n(a) mod3 和 b 代表 n(b)mod3 ，然后使元组的第一个元素大于第二个元素的状态作为最终状态（在这种情况下会有 3 个）.....希望我的回答会有所帮助

Answer 2

我们唯一需要跟踪的是 a 和 b mod 3 分别出现的次数。a mod 3 和 b mod 3 中的每一个都有三种可能性（分别为 0、1 或 2），由于它们是独立的，我们总共可以处于九种状态：

• q00：a mod 3 = 0，b mod 3 = 0
• q01：a mod 3 = 1，b mod 3 = 0
• q02: a mod 3 = 2, b mod 3 = 0
• q10：a mod 3 = 0，b mod 3 = 1
• q11：a mod 3 = 1，b mod 3 = 1
• q12：a mod 3 = 2，b mod 3 = 1
• q20：a mod 3 = 0，b mod 3 = 2
• q21：a mod 3 = 1，b mod 3 = 2
• q22：a mod 3 = 2，b mod 3 = 2

这些将是我们 DFA 的状态。过渡如下：

• 从状态 qij，转换到输入 a 上的 qij'，其中 j' = (j + 1) mod 3
• 从状态 qij，转换到输入 b 上的 qi'j，其中 i' = (i + 1) mod 3

这给了我们总共 18 个转换。

当 a mod 3 > b mod 3 时，我们要接受；那是：

• 状态 qij 接受当且仅当 j > i

这给了我们 3 个接受状态。

最后，当我们看到任一符号的实例为零时，就会出现我们的初始状态；那是：

• 初始状态为 q00

我们现在已经完全定义了这种语言的 DFA。