0

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

L = { w: n a (w) mod 3 > n b (w) mod 3 },

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

4

2 回答 2

0

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

于 2017-02-19T11:40:25.850 回答
0

我们唯一需要跟踪的是 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。

于 2017-02-22T18:34:13.070 回答