摘要：引導(dǎo)學(xué)生關(guān)注學(xué)科前沿，培養(yǎng)學(xué)生理論研究興趣是高校教學(xué)的重要任務(wù)之一。筆者嘗試在編譯原理的教學(xué)中，引導(dǎo)學(xué)生思考關(guān)于計(jì)算的基本問題：如何描述問題，是否有問題沒有算法，等等。文章從編譯原理課程中形式語(yǔ)言與自動(dòng)機(jī)部分內(nèi)容中，引出字符串匹配、自動(dòng)機(jī)等價(jià)測(cè)試、上下文無(wú)關(guān)文法等價(jià)測(cè)試等問題，證明有不可計(jì)算的問題，介紹和分析相關(guān)算法，引導(dǎo)學(xué)生理論研究興趣，拓展課程學(xué)習(xí)深度和廣度。
　　關(guān)鍵詞：?jiǎn)栴}；語(yǔ)言；算法；不可計(jì)算
　　
　　當(dāng)今世界，計(jì)算機(jī)技術(shù)日新月異，滲透到日常生活中的每個(gè)領(lǐng)域。但是就目前技術(shù)而言，計(jì)算機(jī)的能力有沒有極限？有沒有計(jì)算機(jī)解決不了的問題？
　　在編譯原理中，學(xué)習(xí)了形式語(yǔ)言、有限自動(dòng)機(jī)(FA)、上下文無(wú)關(guān)文法(CFG)。這些知識(shí)只是形式語(yǔ)言與自動(dòng)機(jī)理論的基礎(chǔ)部分。然而，這些理論是富有啟發(fā)性的，僅僅利用這些知識(shí)，我們就可以理解為什么有很多問題是沒有算法的，也可以給出相關(guān)的沒有算法的問題舉例。
　　自動(dòng)機(jī)理論是計(jì)算理論的一部分。其內(nèi)容主要包括有限自動(dòng)機(jī)、下推自動(dòng)機(jī)(等價(jià)于上下文無(wú)關(guān)文法)、圖靈機(jī)。前兩者可以視為圖靈機(jī)的簡(jiǎn)化，圖靈機(jī)就是算法的定義。目前計(jì)算機(jī)能做到的事情，圖靈機(jī)都能做到。我們知道有限自動(dòng)機(jī)的能力弱于下推自動(dòng)機(jī)，下推自動(dòng)機(jī)的能力弱于圖靈機(jī)。事實(shí)上，圖靈機(jī)的能力也是有限的。
　　基礎(chǔ)的自動(dòng)機(jī)理論雖然簡(jiǎn)單，但它無(wú)論是在計(jì)算機(jī)領(lǐng)域還是在其它諸多領(lǐng)域都有很重要的應(yīng)用，而且目前也還有很多學(xué)者在從事自動(dòng)機(jī)的理論研究。
　　自動(dòng)機(jī)理論是由應(yīng)用數(shù)學(xué)一代宗師——馮?諾伊曼等人創(chuàng)立起來(lái)的。利用自動(dòng)機(jī)理論，人們?cè)O(shè)計(jì)了很多強(qiáng)有力的算法。例如，對(duì)于字符串匹配問題[1-2] (設(shè)有兩個(gè)字