用于二进制数等效小数的DFA可由3整除

Question

用于生成可被3整除的二进制数的DFA & 5已知我们读取字符串用于例如1下一个0下一个0 100是字符串，并从右到左分配基数2（二进制）......

假设我们读取相同顺序的同一个字符串，但是如果我们读取的是第一位和第0位第二位，所以我们将读为001以上的DFA我们读取字符串相反...所以什么是DFA为此通过从左到右放置位

Answer 1

制作DFA的常用方法是计算这样的东西首先制作一个NFA（sinc eNFA必须更易于组合/交集/ /等），然后将NFA转换为DFA。

那么如何计算二进制数是否可以被3整除？那么，给定base-b中的数字，你可以通过添加mod b-1的数字来轻松地计算mod b-1。给定一个二进制数，你可以通过简单地将它们分组来生成基数。因此对于mod 3，你需要基数4位（比特对）。你可以通过使用3位组来获得mod 7，而mod 15可以使用4组。然后可以将mod 15简单地转换为mod 5和mod 3.

那么如何制作一个添加mod n的NFA呢？您需要一个与值为0..n-1对应的n个状态的循环，并在它们之间进行转换以添加位。对于基体3的情况下，即3个状态

state  00 01 10 11 
    0   0 1 2 0 
    1   1 2 0 1 
    2   2 0 1 2 

这是一个NFA，因此2位过渡经过即未连接否则的中间状态。你的开始和接受状态是0.最后一个细节是处理奇数位。你如何处理这取决于你的号码是大端还是小端。对于little-endian，您希望将最后一个奇数位视为一个数字，因此在0位接受状态时使边缘中间状态转变为0。对于大端序列，您可以添加一个额外的开始状态，在单个0或1位上转换为0和1。

Answer 2

我们可以使用Myhill Nerode定理来指导我们直接使用此语言的最小DFA。

我们首先检查字符串的长度增加，并询问它们是否可以与我们已经看到的字符串区分开来。

如果字符串后面跟着不同的字符串集以获取目标语言的字符串，则字符串是可区分的。

空字符串e后面可以跟着L中的任何字符串以获得L中的字符串。

字符串0也可以跟在L中的任何字符串以获得L中的字符串。我们也可以允许前导0并忽略它们。如果你宁愿让这样的字符串不是你的语言的一部分，那么0就不同于e。我们会让它难以区分。

串1是区分，因为以L不是所有的字符串可以按照它并产生L.字符串事实上，片刻的反思将表明没有字符串以L可以按照1，并导致L.另一个字符串致电< 1>。

我们不需要考虑00和01，因为0与e不可区分，因此00和01与我们已经考虑过的0和1没有区别。

串10是由在这两个0和1既不1也不11区分可以按照它制作在L.字符串调用此< 10>

的字符串11，在另一方面，是完全与e和0没有区别：我们可以在L中添加任何字符串以获得另一个字符串。

我们不需要考虑000,001,010,011,110或111，因为前面已经发现前面没有区分。

字符串100或许令人惊讶地与字符串1无法区分：任何我们可以添加到1以获取L中的字符串的字符串，如果添加到100，也会导致L中的字符串。

串101，也许令人惊讶，从字符串10没有区别：任何事情，我们可以以10〜得到，如果加到101，以及在升的字符串导致升的字符串。

我们命名为三类区分字符串：

• ：E，0，11，等等
• < 1>：1，100等
• < 10>：10，101等

而这些帐户的所有可区分前缀的长度不超过三。 Myhill-Nerode保证有一个最小的DFA，有三个状态对应这些等价类。转换不难更容易理解：如果x = ys，那么对应于y类的状态将导致与符号s上的x类相对应的状态。

Q s Q' 
<e> 0 <e> 
<e> 1 <1> 
<1> 0 <10> 
<1> 1 <e> 
<10> 0 <1> 
<10> 1 <10> 

当然，接受状态是包含L中字符串的状态;只适合这里的法案。初始状态是包含e的状态，在我们的例子中也是如此。

我们现在可以看一下这个，并在数学上合理化规则。为了使讨论更简单，我们定义如下的“三个标记”：

三个标记是输入的子字符串，它表示一个可以被二进制表示法三分的整数。

的状态可以现在可以理解如下：

1. <e>：我们已经看到的通过零的任意数量的分隔的三个的令牌的序列。
2. <1>：我们正在寻找一个不完整的三令牌和我们所看到的部分是一个个全等一个模三个二进制表示。
3. <10>：我们正在寻找一个不完整的三令牌和我们所看到的部分是一个数字conruent的二进制表示两个模三人。

的转换则意义：

1. <e> 0 <e>：丢弃0分三个令牌。（模3）
2. <e> 1 <1>：新的三令牌最初1（mod 3）
3. <1> 0 <10>：部分三令牌变为2（mod 3）。
4. <1> 1 <e>：完成三令牌。
5. <10> 0 <1>：部分三令牌变为1（mod 3）。
6. <10> 1 <10>：部分三令牌保持2（mod 3）。

看到的三令牌的序列是如添加3分别乘以不同的功率的2的倍数;这样的总和保证可以被三除。

如果我们构造一个新的三个标记，读下一个标记s将我们当前的值v乘以2，然后加上s;即v' = 2v + s。只有这样，v'可以通过3整除是，如果v是1 (mod 3)和s是1.我们可以忽略的情况下v是0 (mod 3)和s是0，因为在这种情况下，我们都在<e>和三标记之间阅读0秒。