从字母{a，b，c}构建DFA

Question

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

因此，它可以接受：AAA，BBB，CCC，AB | BB，caaac，ccbbbcc，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：初始状态下接受的，B公司和C公司的任何前缀。指出，仅可通过串用BB作为一个子访问
• Q3，Q6：
• Q1，Q4：那只能由弦与AA作为一个子访问
• Q2，Q5状态的状态可能只能由具有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]是可区分的，因为它可以后跟一个L + L来获得一个字符串L.调用它的状态[aa]。
5. 字符串bb和cc同样是可区分的并且具有状态[bb]和[cc]。
6. ba和ca是无法区分的;它们后跟与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相同的状态数量 - 这恰好消除了非确定性。

• 我们得到转换的方式是从状态[x]到状态[y]上的符号s是通过查看xs是否与z不可区分。
• 我们得到初始状态的方式是它总是[e]。
• 的方式，我们得到了接受状态是它是唯一一个，其字符串后面可以通过电子邮件获得一个字符串L.