正規語言概論 – 交大修課心得

課程資料

正規語言概論

開課：黃廷祿老師

修課年度：100資工系

這門課的課題是基礎的計算理論，研究什麼是電腦的能力和極限。介紹各種計算模型，例如 DFA, NFA, PDA, Turing machines 等等，以及其相對應的正規語言，如 regular languages, context free languages, Turing-decidable languages 等等。也會探討問題間的 Reduction 以及問題的 Complexity。使用的課本是《Introduction to the Theory of Computation》，更多相關議題可參考：〈正規語言概論〉。

上課方式

上課是用老師自己編的講義作為投影片講解，有時也會配合課本的頁面。老師上課時常會點同學回答，如果有同學打瞌睡他也會熱心的叫醒大家。老師會記人的名字，筆者就曾被點名回答題目。有時老師的穿著頗為正式，下課時如果問老師問題，他會不耐其煩的細心講解。作業通常是先在上課時宣佈，其後再公佈於課程網頁上。他偶而會在上課時突擊小考。

他曾說資工有很多課會消失於時代的演進之中，但這堂課是歷久不衰的。

好像是因為有同學懷疑課本的文法，所以老師有一次和我們談談學習英文的重要性，還跟我們說學校的圖書館有 iPad 可以出借，介紹了可以在其上使用的 Merriam-Webster 英英字典(有真人發音)，以及 New York Times 等讀物。

順帶一提，筆者也有用過《Longman Dictionary of Contemporary English》以及《Collins COBUILD Advanced Learner’s English Dictionary》，這三者都是非常優秀的英英字典，除了紙本外也都附有 PC 版光碟。關於英英字典也可參考：〈辭典選用的基本觀念〉、〈哪本辭典的定義最好？〉

考試作業

這堂課的負擔其實沒有很重，通常是數個禮拜老師才會在上課時宣佈習題。習題內容為課本的練習題，每次都只有一兩題，很快就會寫完，有時老師也會自己出題。

基本上是不點名，只有一次發了問卷調查作為點名，不過因為上課時有突擊小考，加上作業都在上課先宣佈的關係，建議還是不要蹺課比較好。

突擊小考的內容多半是剛剛才講過的內容，所以上課專心能有回報。考題不難，通常只有一題，若對課本有一定的熟悉度，應能很快寫完。

除此之外，還有期中考和期末考。老師會在事前公佈考古題，從考古題看來，以前的考試型態似乎有不少證明題。不過這次的期中考意外的沒出證明題，而且題型偏向簡單，多數人都考的不錯。期末考出了幾題證明，不過也滿基本的，考古題感覺難很多。

考試題型分別為是非題、選擇題，及最後的簡答、計算與證明題。所有的考試都是 open book，可以自由查閱課本、講義，或任何自帶紙本參考資料。也因此考的題目都會有變化，不會跟考古題一樣。

結語

這門課使用的課本其實內容不多，而且由於較為理論與數學，可以邊看邊思考，閱讀起來並不枯燥，筆者暑假時利用通勤的時間，把課本看完了一遍，覺得幫助頗大。《Intro. to the Theory of Computation》這本書真的寫得不錯，算是在資工教科書中，十分易讀的課本之一。

由於老師出的練習題實在太少，令人感覺不踏實，所以筆者也將課本裡附有答案的習題寫過了一遍。老師並不會出一些刁難的問題，基本上只要細讀課本與講義，考試和作業應該都能把握。