有限状态自动机中的被动学习

Question

我正在阅读《机器学习基础》中的以下段落（本书的第362页的https://cs.nyu.edu/~mohri/mlbook/。

现在，我对DFA的概念还很陌生，但是我有一些经验。我对该段有疑问。

1. 他们为什么要使用确定性自动机，该自动机接受带有正标记的字符串“ a”或“ b”？您肯定要拒绝$“ b” $，因为它带有负面标签吗？

2. “ a”是一个字符串，即a = 01010101还是单个字母？

3. 接受“ a”或“ b”的最小两个状态自动机是什么？我也不确定它与它们接下来针对a *语言描述的单状态机有何不同？有人可以明确描述两者吗？我看不到这两种情况之间的区别是什么，也许这就是为什么我不明白为什么一个有两个状态而另一个有一个状态的原因。

我非常感谢您提供的任何帮助，因为我确实试图理解他们所谈论的概念。

Answer 1

1. 他们希望DFA具有尽可能少的状态，可以接受字符串'a'并拒绝字符串'b'
2. 'a'表示符号a，而不是表示您提供的位字符串的速记。在形式语言理论中，允许使用字母作为符号。
3. [他们试图在此处区分接受状态为“ a”和拒绝状态“ b”的DFA最少的国家，以及接受语言{'a'}的最小DFA。见下文。

最小的接受“ a”但拒绝“ b”的DFA实际上具有两种状态，如果使用标准约定，必须表示无效状态并且必须显示所有转换：

       +--a--+
       |     |
----->q0<----+
       |
       b
       |
       V
      q1<----+
       |     |
       +-a,b-+

在上述DFA中，q0正在接受。较小的DFA不会接受“ a”而拒绝“ b”。您知道这一点，因为DFA必须具有一个接受状态才能接受任何东西，而一个非接受状态则必须拒绝任何东西，并且由于一个状态不能同时存在，因此我们需要两个。现在，引用的段落所得到的区别是，接受语言{'a'}的DFA更大（因为它排除了除了'a'以外的所有内容，而不仅仅是'b'）：

----->q0--a-->q1
      |       |
      b      a,b
      |       |
      |       V
      +------>q2<---+
              |     |
              +-a,b-+

这里，q1正在接受。注意，我们需要一个额外的状态，以避免接受更长的'a'字符串。