從字母{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.