# 台大 110 軟體
###### tags: `NTU` `110` `軟體`
1. D
2. A
3. A
4. C
5. A
6. B
7. B
8. A
9. C
10. A
11. C
12. D
13. B
14. B
15. D
16. D
17. B
18. D
:::warning
可以利用 NFA 轉 DFA 演算法的概念思考。想知道細節可以讀[這本](https://www.amazon.com/Introduction-Automata-Languages-Computation-Hardcover/dp/B00M8P8LA6)，這邊簡單帶過思考過程。

首先觀察 ['A'][3] = 4 這格，這意味著「若在第 3 個位置匹配到 A，就往 4 前進」，代表第 3 個字元是 A。同理可推其它的：

_ _ _ A A _ B _ _ C

再來觀察 ['B'][9] = 3，「若在第 9 個位置匹配到 B，則往 3 前進」意味著 0, 1 和 7, 8 是相同的，而且第 2 個位置是 B：

_ _ B A A _ B _ _ C

同理可觀察 ['A'][6] = 2，代表第 0 個位置與第 5 個位置相同、且第 1 個字元為 A:
_ A B A A _ B _ _ C

而第 8 個字元跟第 1 個字元是相同的...：
_ A B A A _ B _ A C

而第 0、5、7 的字元是一樣的，所以只要推出其中一個就可以了。接著考慮 ['B'][3] = 0 和 ['C'][3] = 0，這兩個意味著「在第 3 個位置匹配到 B 或 C 的話，就前進到 0」也就是要重新匹配。這代表第 0 個位置不會是 B 或 C，不然應該有一個要前進到 1 才對。所以第 0 個是 A：
A A B A A A B A A C

A 總共有 7 個
:::
:::info
NFA 在匹配的時候，同時間有「好幾個」匹配在進行。匹配成功的就保留，失敗的就丟掉。

以 ['B'][9] = 3 為例，同時有 2 個匹配在進行，一個在匹配第 9 個，另一個在匹配第 2 個。而第 9 個失敗了，第 2 個卻成功了，所以前進到 3。這代表第 2 個是 B，而且 [0] = [7], [1] = [8]
:::
19. A
20. C