computer-science - 从字母表 {a,b,c} 构建 DFA 的最佳方法是什么？

Question

我正在尝试在字母表 {a,b,c} 上构建一个 DFA，接受具有三个连续相等字母的所有字符串的集合。

例如它可以接受:aaa、bbb、ccc、abbb、caaac、ccbbbbcc、aaabbbc..

我尝试了不同的方法，但它变成了一个巨大的图表，我想知道是否有一种更优雅的方法来做到这一点？

Answer 1

首先，您的标题显示为 NFA，但问题正文显示为 DFA。我会回答这两种方式来说明为什么这很重要。

首先考虑 NFA。我们只想接受具有三个连续的同类符号的字符串。存在三个符号，因此可以通过三种方式发生这种情况(假设我们认识到在第一次出现三个连续符号后将接受该字符串)。我们可以看到任何东西，然后看到三个相同的符号，然后再次看到任何东西。 NFA 很容易写下来:

     __
    /  \                  __
    |  / a,b,c           /  \
    V /                  |  / a,b,c
--->q0--a->q1-a->q4-a-\  V /
    | \-b->q2-b->q5-b-->(q7)
    \---c->q3-c->q6-c-/

我们的州执行以下操作:

• q0:初始状态接受 a、b、c 的任何前缀。
• q1、q4:表示只能被以 aa 为子串的字符串访问
• q2、q5:表示只能被以 bb 为子串的字符串访问
• q3、q6:表示只能被以 cc 为子串的字符串访问
• q7:接受状态，只能由以 aaa、bbb 或 ccc 中的任何一个作为子字符串的字符串访问。

读取输入字符串的某些前缀后，NFA 会不确定地分支以检查输入字符串是否包含 aaa、bbb 或 ccc，如果包含，则输入 q7 并接受后缀中可能剩余的任何内容。

为了获得 DFA，实际上是最小的 DFA，我建议按照 Myhill-Nerode 定理继续进行，按字典顺序检查字符串，看看它们是否可以与我们已经考虑过的字符串区分开来，因此在一个状态下设计我们的 DFA时间。

1. 空字符串是可区分的。后面可以跟L中的任意字符串，得到L中的一个字符串，称其状态为[e]。
2. 字符串 a 与空字符串不同，它后面可以跟 aaL + L 得到 L 中的字符串。称其状态为 [a]。
3. 字符串 b 和 c 同样是可区分的，并且具有状态 [b] 和 [c]。
4. 字符串 [aa] 是可区分的，因为它后面可以跟 aL + L 以获得 L 中的字符串。称其状态为 [aa]。
5. 字符串 bb 和 cc 同样可以区分，并且具有状态 [bb] 和 [cc]。
6. ba 和 ca 与 a 无法区分；它们后面跟有与 a 相同的字符串，以得到 L 中的字符串。
7. ab/cb 和 ac/bc 同样分别与 b 和 c 无法区分。
8. aaa 是可区分的，因为它后面可以跟任何内容，并且在语言中它仍然是一个字符串。
9. bbb 和 ccc 与 aaa 没有区别。
10. 所有其他长度为 3 的字符串与 a、b、c、aa、bb 或 cc 无法区分(选中此项)
11. 所有以 aaa 开头的长度为 4 的字符串与较短的字符串无法区分(检查此项)

因为我们用完了可区分的字符串，所以我们知道我们已经列出了最小 DFA 的所有必要状态，并且我们可以写下答案:

               +---a--->[a]<---a----+
               | +-c--->[c]<---c-+  |
               | |               |  |
     +----b--->[b]-------b------>[bb]---b----+
     |                                       |
     |         +---b--->[b]<---b----+        |   +--+
     |         | +-c--->[c]<---c-+  |        |   |  a,b,c
     |         | |               |  |        V   V  |
--->[e]---a--->[a]-------a------>[aa]---a--->[aaa]--+
     |                                       ^
     |         +---a--->[a]<---a----+        |
     |         | +-b--->[b]<---b-+  |        |
     |         | |               |  |        |
     +----c--->[c]-------c------>[cc]---c----+

(状态 [a]、[b] 和 [c] 各重复两次，以使图表更漂亮。事实上，状态转换图不是平面的，渲染起来会很困惑，更不用说在 ASCII 艺术中了)。

请注意，这与我们写下的简单 NFA 具有相同数量的状态 - 这恰好消除了非确定性。

• 我们获得转换的方法是通过符号 s 从状态 [x] 到状态 [y]，通过查看 xs 是否与 z 无法区分。
• 我们获得初始状态的方式是它始终是 [e]。
• 我们获得接受状态的方式是它是唯一一个其字符串可以跟在 e 后面以获取 L 中的字符串。