解决并证明一个 DFA 减去两个元素的模数

Question

我在研究计算理论 class 我们被要求编写的证明之一具有以下参数：

L = {a, b}, x ε {a, b}*, c ε {a, b}。 #c(x) 定义为字符 c 在 x 中出现的次数。

A = {x | #a(x)-#b(x) = 0 mod 3}。

我对一般的 DFA 很清楚，但是被包含的减法绊倒了。在证明这样的事情时，是只用案例更好，还是试着画一张图更好？我不确定我应该从哪里开始实际绘制...它会涉及多个单独的流程吗？

感谢任何帮助！

Answer 1

我会建议，在这种情况下，您直接使用 Myhill-Nerode 定理，要么找到该语言的最小 DFA 中的状态数，要么发现该语言是非常规的，因为它需要无限多个状态。

如果您从未听说过 Myhill-Nerode 定理，您可能听说过字符串与语言的不可区分性关系。两个字符串 x 和 y 对于语言 L 是不可区分的，如果对于任何字符串 w 使得 xw 在 L 中，yw 也在 L 中，反之亦然。不可区分的字符串属于关于不可区分关系的等价 classes，并且这些 classes 直接对应于语言的最小 DFA 的状态（如果有有限多个等价 classes，就是这样！）。

为了使用它，我们开始检查字符串的字典序递增，直到我们发现对于长度为 k 的字符串，我们没有引入新的等价 classes w.r.t。不可区分性（或者我们认识到某种模式告诉我们将有无限多个等价 classes）。

空字符串后面可以跟L中的任意字符串，得到L中的字符串（平凡）。对于空字符串，我们总是有一些等价的 class。这相当于说任何 DFA 必须至少有一个状态——初始状态。注意：空字符串在我们的语言中是因为 0 - 0 = 0 (mod 3)。如果我们得到一个 DFA，对应于这个等价 class 的状态将被接受。调用等价 class 并声明 [e].
字符串a后面不能跟任何语言中的字符串(1 - 0 != 0 (mod 3))，所以我们已经知道等价的class 必须不同于 [e]。可以跟在这个后面的字符串和可以跟在空字符串后面的字符串一样，只是这些必须满足#a(x) - #b(x) = 2 (mod 3).
字符串b后面不能跟任何语言中的字符串(0 - 1 != 0 (mod 3))，所以我们知道这是一个新的class [b]。事实上，字符串b后面的字符串必须满足#a(x) - #b(x) = 1 (mod 3)才能在语言中将字符串b引到1
字符串aa后面不能跟任何语言中的字符串(2 - 0 != 0 (mod 3))，所以我们知道这不是class [e]。然而，稍加思考就会发现，这个字符串与字符串 b 无法区分，因为任何将字符串 aa 转换为该语言中的字符串的字符串也会将字符串 b 转换为该语言中的字符串，并且反之亦然。考虑：(aa)a, (aa)bb, …;对比：(b)a, (b)bb, ….由于 aa 与 b 没有区别，我们不添加新的等价物 class 或声明它。
字符串 ab 与空字符串没有区别，因为 L 中的任何字符串都可以添加到它以得到 L 中的另一个字符串。不需要定义新的等价关系 class。
字符串ba和ab没区别；同样，不需要新的等价物 class。
字符串bb与字符串a无法区分：(bb)b, (bb)aa, …;与 (a)b、(a)aa、...

在考虑长度为 2 的字符串时，我们不需要引入任何新的等价 classes；这意味着我们完成了，我们正在考虑的语言是常规的。它具有对应于等价 classes [e]、[a] 和 [b] 的状态。此外，我们可以通过查看什么状态对应于状态的代表字符串（空，a 或 b）和转换中的符号的串联等价 class 来获得转换。

将 a 连接到空字符串上得到字符串 a，因此符号 a 从 [e] 到 [a] 有一个转换，因为 a = e.a；
将 b 连接到空字符串上得到字符串 b，因此符号 b 从 [e] 到 `[b] 有一个转换，因为 b = e.b;
将a拼接到a上得到字符串aa，aa和b没有区别；因此，由于 aa = a.a 和 aa ~ b;

[a]

[b]

将b与a拼接得到字符串ab，ab与空字符串没有区别；因此，由于 ab = a.b 和 ab ~ e;

[a]

[e]

将a连接到b得到字符串ba，ba与空字符串没有区别；因此，由于 ba = b.a 和 ba ~ e;

[b]

[e]

将b连接到b得到字符串bb，bb与字符串a没有区别；因此，由于 bb = b.b 和 bb ~ a.

[b]

[a]

生成的 DFA 如下所示：

           b
       /--------\
       |        |
       |  /--->[a]
       V / a   | ^
----->[e]     a| |b
       ^ \ b   V |
       |  \--->[b]
       |        |
       \--------/
           a

解决并证明一个 DFA 减去两个元素的模数

Solving and proving a DFA that subtracts and takes the modulus of two elements

automata

finite-automata

subtraction

dfa

computation-theory