《自動機理論、語言和計算導論》學習第 14 天，p428-p525總結，總計 98 頁。
一、技術總結
1.Kruskal's algorithm(克魯斯克爾算法)
2.NP-Complete Problems
p434, We say L is NP-complete if the following statements are true about L:
(1)L is in NP。
(2)For every language L' in NP there is a polynomial-time reduction of L' to L。
3.QBF
quantified boolean formulas。
二、英語總結
1.couch
v. couch sth in/as sth: to express sth in a particular way。
eg: I don't understand this form- it's all couched in legal terminology。
2.conservatively
(1)conserve: con-(assimilated form of com-) + *ser-(to protect)。由“protect”引申出“maintain”之意。
(2)conservative: adj. not usually liking or trusting change, especially sudden change。
(3)conservatively: adv. in a way that is not fashionable.
3.deceptively
(1)deceive: vt. to persuade sb that sth false is the truth。
(2)deceptive：adj. misleading。
(3)deceptively: adv. in a way that is deceptive。
eg: The plan seemed deceptively simple(=it seemed simple but was not)。
4.permutation
(1)permute:per-(thoroughly) + mutare(to change)。vt. to change one for another。
eg: We wish to permute the order of the bytes。
(2)permutation: n. ways in which a set of things can be ordered(數學上的“排列”)。
eg: There are 120 permutations of the numbers 1, 2, 3, 4 and 5; for example, 1, 3, 2, 4,5 or 5, 1, 4, 2, 3。
5.slight
adj. small in amount or degree。Slight is sometimes used with abstract noun to describe amounts or degree of change that are small and not important。
6.adequate
ad-(to) + equal。adj. equal to what is needed or desired, sufficient； enough or satisfactory for a particular purpose。
7.instinct
in-(in) + stinguere(prick, goad)。n. the way people or animals naturally react without having to think or lean about it。
eg: Her first instinct was to run。
三、其它
歷時14天，500多頁的《自動機理論、語言和計算導論》算是看完了，這些算是編譯原理的前導知識，對自動機、正則表達式、語言、上下文無關語法、P和NP問題有了一個初步的認識與瞭解，談不上掌握，更談不上深入。如果你問我書中的xxx習題怎麼解，那我只能如實回答：不會。
每天發這些學習筆記，對讀者而言，其實意義並不大，幫助很小。如果要説有什麼意義，那麼可能就是起到一個示例的作用，在編程這條路上，我在做什麼，我是怎麼做的。
雖然這些“基礎”學起來很難，但我會努力，感謝那麼久以來一直還關注的讀者沒有取關。
四、參考資料
1. 編程
(1)Eric S.Roberts，《自動機理論、語言和計算導論(英文版.第3版)》：https://book.douban.com/subject/2274854/
2. 英語
(1)Etymology Dictionary：https://www.etymonline.com
(2) Cambridge Dictionary：https://dictionary.cambridge.org
歡迎搜索及關注：編程人(a_codists)
