finite-automata - 关于有限状态自动机的问题

Question

我想构造一个接受以下语言的确定性有限自动机：

{w ∈ {a,b}* : w 中的每个 a 都紧跟在 ab 前面}

到目前为止，我已经得到 >⨀ ---b---> O ---a---> O。

'>' = 初始状态

⨀ = 最终状态

Answer 1

考虑 FA 的一个好方法是尝试考虑您可以处于多少种不同的情况，就您将如何获得语言中的字符串而言。让我们从几个小字符串开始，看看我的意思。

假设您从空字符串开始。你可以附加什么来获得语言中的字符串？好吧，空字符串是语言中的，所以我们可以附加空字符串（即，什么都没有）并且还有一个语言中的字符串。此外，我们可以将我们要使用的语言中的任何字符串附加到空字符串中，我们将获得该语言中的字符串（很简单）。我们将需要至少一种状态来记住空字符串（以及类似的字符串 - 我们可以将空字符串或该语言中的任何其他字符串附加到该字符串并且仍然具有该语言中的字符串）；这将是开始/初始状态，并且由于空字符串在语言中（我们很容易检查），我们知道开始/初始状态将被接受。

现在让我们考虑字符串 a。这是一个不在该语言中的字符串的示例，我们无法在该字符串的末尾添加任何内容以使其成为该语言；我们已经违反了字符串中所有 a 都以 b 开头的条件。我们可以添加到其中以获得语言中的字符串的字符串集是空集，因此，我们需要一个不同于我们已经识别的状态来记住这个字符串和类似的字符串 - 字符串我们不能添加任何东西来获取语言中的字符串。

回顾一下，我们已经确定了两种状态：接受的开始/初始状态，以及我们所说的“死”状态——一种不接受且永远不会导致接受状态的状态。

让我们试试字符串 b。这个字符串是语言，所以我们可以给它添加空字符串。我们还可以简单地将语言中的任何其他字符串添加到该字符串的末尾，并获取该语言中的另一个字符串。但是，我们也可以在该语言中的任何字符串后添加一个 a，并获取该语言中的另一个字符串。例如，我们可以添加字符串 a 后跟 bbabb 以获得 babbabb，这也是语言中的。因此，我们可以添加的字符串集合是我们以前从未见过的集合，我们需要一个新的状态来表示这个字符串 - 字符串 b - 以及类似的字符串。它将接受，因为字符串 b 是语言中的字符串。

您应该尝试使用字符串 aa、ab、ba 和 bb。您应该会发现字符串 aa 和 ab 都已经被我们的死状态所覆盖（我们不能在它们的末尾添加任何字符串来获取我们语言中的任何内容），并且字符串 ba 被 start/initial 覆盖状态（我们只能添加到该语言中已经存在的字符串以获取该语言中的其他字符串），并且该 bb 对应于我们识别的第三个状态（添加任何字符串，或单个 a 后跟任何字符串，将导致 a字符串也在语言中）。由于我们已经用尽了所有长度为 2 的字符串并且没有添加任何新状态，因此我们知道这些是我们在 FA 中需要的所有状态；我们可以添加其他人，但它们是不必要的。

要获得转换，我们需要做的就是确保所有状态都指向正确的位置。换句话说，由于字符串 a 是通过在空字符串的末尾添加字符 a 形成的，所以我们需要从 start/initial 状态（对应于空字符串）过渡到 dead 状态（对应于字符串 a ) 当 FA 读取符号 a 时发生。同样，我们需要从开始/初始状态到符号 b 上的第三个状态的转换。其他转换也类似：在 a 或 ab 上，死状态转换到自身，第三个状态在 b 上循环并转换到 a 上的开始/初始状态。一旦每个状态对字母表中的每个符号都有一个转换，你就有一个完整的（和正确的）FA。此外，通过以这种方式构建它，

Answer 2

状态 1（接受，初始状态）：

• 在输入“a”时，转到状态 3（永久拒绝字符串）
• 在输入“b”时，转到状态 2

状态 2（接受）：

• 在输入“a”时，转到状态 1
• 在输入“b”时，转到状态 2

状态 3（不接受）

• 在输入“a”或“b”时，保持状态 3

从概念上讲，状态 1 表示“最后一个字母不是 b 的有效字符串”，状态 2 表示“最后一个字母是 b 的有效字符串”，状态 3 表示“无效的字符串”

以图表形式：