请帮我制作以下条件的DFA:
L = { w: n a (w) mod 3 > n b (w) mod 3 },
其中 n a (w) 表示a
in w 的出现次数,n b (w) 表示b
in w 的出现次数。
请帮我制作以下条件的DFA:
L = { w: n a (w) mod 3 > n b (w) mod 3 },
其中 n a (w) 表示a
in w 的出现次数,n b (w) 表示b
in w 的出现次数。
首先为 n(a)mod3 水平设计 DFA,并将其初始状态设计为垂直 n(b)mod3 .....总共需要 9 个状态并标记状态 (a,b),其中 a 是 n(a) mod3 和 b 代表 n(b)mod3 ,然后使元组的第一个元素大于第二个元素的状态作为最终状态(在这种情况下会有 3 个).....希望我的回答会有所帮助
我们唯一需要跟踪的是 a 和 b mod 3 分别出现的次数。a mod 3 和 b mod 3 中的每一个都有三种可能性(分别为 0、1 或 2),由于它们是独立的,我们总共可以处于九种状态:
这些将是我们 DFA 的状态。过渡如下:
这给了我们总共 18 个转换。
当 a mod 3 > b mod 3 时,我们要接受;那是:
这给了我们 3 个接受状态。
最后,当我们看到任一符号的实例为零时,就会出现我们的初始状态;那是:
我们现在已经完全定义了这种语言的 DFA。