序 - 計算理論是計算機科學的靈魂
我就讀大一、大二時，其實對資訊科學並沒有非常的喜歡，而比較喜歡數學和物理這種用「單純」且「優雅」的理論就能解釋許多現象的學科。一直到大三學到了正規語言概論，才感覺到自己真正初步了解「電腦」的能力與極限，讓我有一種豁然開朗的感覺，而開始對資訊科學感興趣。
上了研究所後，又因修課仔細的研讀了一次正規語言，感觸十分深刻，因此，寫下了這些正規語言的介紹和整理。我的介紹整理秉持盡量以中文撰寫英文為輔為原則，期望有更多人能參透正規語言這個有趣的學門：）
目錄
一、正則語言 Regular Languages
- Ch1 決定性有限自動機 Deterministic Finite automata, DFA
- Ch2 非決定性有限自動機 Nondeterminism Finite automata, NFA
- Ch3 正則表達式 Regular Expression, RE
- Ch3.5 常用的正則表示式 Regular Expression in Application
- Ch4 泵引理 Pumping Lemma
- Ch5 邁希爾－尼羅德定理 Myhill-Nerode Theorem
二、上下文無關語言 Context-Free Languages
- Ch6 上下文無關語言 Context-free language, CFLs
- Ch7 下推自動機 Pushdown automaton, PDAs
- Ch8 上下文無關語言泵引理 Pumping lemma for context free languages
三、邱奇－圖靈論題 Church–Turing Thesis
四、決定性問題 Decidability
- Ch11 決定性問題 Decidability
- Ch12 不可決定問題與圖靈可識別語言 Undecidable Problem and Turing-recognizable language
- Ch12.5 決定與不可決定問題相關習題
五、歸約 Reducibility
六、時間複雜度 Time Complexity
- Ch15 複雜度P和NP Time Complexity, P and NP
- Ch16 NP完全 NP-Complete, NPC
- Ch16.5 Cook-Levin理論與卡普的二十一個NP-完全問題
前言
正規語言概論是交大資工大三上的必修課程。這門課的課題是基礎的計算理論，研究什麼是電腦的能力和極限。介紹各種計算模型，例如 DFA, NFA, PDA, Turing machines 等等，以及其相對應的正規語言，如 regular languages, context free languages, Turing-decidable languages 等等。也會探討問題間的 Reduction 以及問題的 Complexity 等等。
通常使用的教科書主要是《Introduction to the Theory of Computation》不過也有老師使用《Introduction to Automata Theory, Languages, and Computation》。
簡介
透過計算模型，我們可以對計算定下明確的數學定義。而一旦有了明確的定義，便可以研究什麼是可計算的、什麼是不可計算的，而對於可計算的問題，必須花費多少時間和空間才可能計算。
Church–Turing thesis 指出，所有演算法可解的問題，都可透過 Turing machines 求解，也因此，藉由研究 Turing machines 我們得以探討電腦的極限，以及對各種問題的難度訂出明確的界線。
這是一門非常理論與數學的課，需要非常清晰的邏輯思考。老師曾說，資訊界日新月異，許多課程可能幾年後就不見了，或者教的東西大幅改變。但你幾乎可以確定，正規語言這門課還是會一直存在。從哲學的角度來說，計算理論在電腦科學裡佔了十分核心的地位。
正規語言課程所學的東西其實也有很多延伸的應用，以至於很多讀者很可能早已接觸過某些部份，但直到這門課，才真正以嚴謹的方式學習背後的來歷。像是如果有接觸像 Python 等語言或者用過 Vim 等編輯器的搜尋功能的讀者，很有可能有接觸過正規表示式。而 CFG 和程式語言的設計以及編譯器等課程有密切相關，你或許會曾在程式語言的文件上看過他。如果在演算法等課程聽過 NP、P 等名詞，在這堂課裡，你可以學到這些名詞到底有什麼含意。而對什麼是演算法，時間複雜度、問題的可計算性等等，都會在這堂課得到更深的理解。
References
交資夢想 - 正規語言概論
https://nctucs.wordpress.com/2011/12/10/formal-languages/
發表文章
