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 回答