###### tags: `compiler` `note` `thu`
# Regex至DFA的轉換(含化簡)
### 本頁使用$(a\ |\ b)^*abb$做為操作的範例。

## 1. Regex至$\epsilon$-NFA
### a. Regex語法
- `|`: 「或」的意思。
- `*`: ***Kleen closure***, 可包含所有集合內的元素字串組合。(含空集$\phi$)
- `+`: 類似***Kleene closure***, 但不包含空集$\phi$。
- 直接相接，e.g. $r_1r_2$, 其中$r_1$

### b. $\epsilon$-NFA和Regex語法的對應

### c. 合在一起
- 先分析regex，將其轉換成多個小的NFA
- 用$\epsilon$把小NFA們按語法連結起來。
- 檢查路徑是否有包含closure的要求(e.g. 7->0的$\epsilon$)

## 2. $\epsilon$-NFA至DFA
- `e-closure`: 透過$\epsilon$的移動可以逹到最遠的節點集合。

### a. 從起始狀態開始觀察NFA對於輸入的狀態變化。

#### 起點:

e-closure(0): {2, 4, 7} -> (STATE 0)

#### 分支:
##### 1. 先吃a

move({2, 4, 7}, a) = {3, 8}
e-closure({3, 8}) = {2, 4, 7, 8} -> (STATE 1)

- 再吃a: 不動
- 再吃b:

    move({2, 4, 7, 8}, b) = {5, 9}
    e-closure({5, 9}) = {2, 4, 7, 9} -> (STATE 2)

- 再吃a:

        move({2, 4, 7, 9}, a) = {3, 8}
        e-closure({3, 8}) = {2, 4, 7, 8} -> (STATE 1)

- 再吃b:

        move({2, 4, 7, 9}, b) = {5, 10}
        e-closure({5, 10}) = {2, 4, 7, 10} -> (STATE 3) (ACCEPTED)

- 再吃a: STATE 1
- 再吃b: STATE 0

##### 2. 先吃b

move({2, 4, 7}, b) = {5}
e-closure({5}) = {2, 4, 7} -> (STATE 0)

### b. 把整理結果畫成圖

## 3. DFA狀態數最小化(化簡)