2

我该如何设计 DFA：

Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

十进制数字集。

L = {w| The decimal number represented by w leaves an odd remainder when divided by seven.}

到目前为止，我已经（手）画出了七个状态（q0 - q6），其中奇数个 q 状态正在接受。

我从这里去哪里？

4

1 回答 1

1

我将分两步构建它：

  1. 构造一个 DFA，其状态跟踪 w 除以 7 时的余数。您可以通过构造状态 0、1、2、3、...、6 并将它们链接如下来做到这一点：如果 w 除以 7 时留下 r 的余数并且下一个数字是 d，那么您想要结束处于对应于 10r + d (mod 7) 的状态。这将提供来自每个州的十个传出链接。计算这些链接会很烦人，但你只需要做一次。

  2. 马克将 1、3 和 5 声明为接受，其他所有内容为拒绝。

希望这可以帮助！

于 2014-06-01T19:57:55.627 回答