2015年6月14日 星期日

[系列文目錄] 正規語言 Formal Language

 


序 - 計算理論是計算機科學的靈魂


我就讀大一、大二時,其實對資訊科學並沒有非常的喜歡,而比較喜歡數學和物理這種用「單純」且「優雅」的理論就能解釋許多現象的學科。一直到大三學到了正規語言概論,才感覺到自己真正初步了解「電腦」的能力與極限,讓我有一種豁然開朗的感覺,而開始對資訊科學感興趣。

上了研究所後,又因修課仔細的研讀了一次正規語言,感觸十分深刻,因此,寫下了這些正規語言的介紹和整理。我的介紹整理秉持盡量以中文撰寫英文為輔為原則,期望有更多人能參透正規語言這個有趣的學門:)




目錄


一、正則語言 Regular Languages


二、上下文無關語言 Context-Free Languages


三、邱奇-圖靈論題 Church–Turing Thesis


四、決定性問題 Decidability


五、歸約 Reducibility


六、時間複雜度 Time Complexity





前言


正規語言概論是交大資工大三上的必修課程。這門課的課題是基礎的計算理論,研究什麼是電腦的能力和極限。介紹各種計算模型,例如 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/







技術提供:Blogger.