認知方法在形式語言與自動機理論教學(xué)中的應(yīng)用

摘要：在形式語言和自動機理論的教學(xué)活動中，合理地應(yīng)用歸納和演繹方法，對于計算思維能力的培養(yǎng)有重要作用。本文介紹了我院這方面的教學(xué)實踐和經(jīng)驗。

關(guān)鍵詞：計算思維能力；歸納和演繹；理論教學(xué)

中圖分類號：G642文獻標(biāo)識碼：B

1歸納和演繹是兩種認知的科學(xué)方法

以學(xué)校為例，最初認識是“學(xué)校”這樣一個詞。在對其進行分類的過程中就可以不斷理解這一詞的含義。進一步知道學(xué)校有大學(xué)、中專、中學(xué)和小學(xué)之分； 再進一步又知道大學(xué)分綜合性大學(xué)，理、工、農(nóng)、醫(yī)、文科大學(xué)等；每一學(xué)科分又為不同專業(yè)，專業(yè)分為不同方向。這就是從一般到特殊的演繹方法。

一條黃狗，一條白狗，除了顏色不一樣外，其他有關(guān)狗的特征完全一樣，這樣，可以構(gòu)造一個類：“狗”，其中描述了狗的所有共同特征，比如：會叫，具有犬齒，嗅覺靈敏，具有顏色，忠實等。這就是從特殊到一般的歸納方法，在本科階段的學(xué)習(xí)過程中，學(xué)生以觀察、描述、比較、分類、推斷、應(yīng)用、創(chuàng)造思維等科學(xué)思維過程為主，強調(diào)自學(xué)的能力在培養(yǎng)；研究生階段，需要對學(xué)生進一步進行抽象思維、邏輯思維、創(chuàng)造思維能力的培養(yǎng)。

計算機科學(xué)與技術(shù)學(xué)科強調(diào)4個方面的專業(yè)能力：計算思維能力、算法設(shè)計與分析能力、程序設(shè)計與實現(xiàn)能力、計算機系統(tǒng)的認知、分析、設(shè)計和運用能力。這也是計算機科學(xué)與其他學(xué)科的重要區(qū)別。相關(guān)的理論是計算機學(xué)科的基礎(chǔ) [1]。

計算機科學(xué)與技術(shù)學(xué)科要求學(xué)生具有形式化描述和抽象思維能力，要求掌握邏輯思維方法。這種能力就是計算思維能力或計算機思維能力。形式語言與自動機理論課程是培養(yǎng)計算思維能力的重要課程。認知方法提供了從一般到特殊的演繹手段，又提供了從特殊到一般的歸納形式。這種分類、歸納的方法在在形式語言與自動機理論課程的教學(xué)中是很重要的。

2形式語言理論中的歸納和演繹

采用一般到特殊的演繹方法，提出比較通用的文法構(gòu)造方法，再具體討論不同語言對典型文法的應(yīng)用情況。進一步總結(jié)文法一般性的構(gòu)造方法，學(xué)生難以理解和掌握的文法構(gòu)造方法，不再是難題。

一般地，對于字母表∑，

對任意的a，b∈∑+，可以使用A→ab|aAb來產(chǎn)生{anbn|n>0}；

對任意的a，b∈∑+，可以使用A→a|b|aA|bA來產(chǎn)生{a，b}+；

對任意的a∈∑+，可以使用A→a|aA來產(chǎn)生{an|n>0}；

對任意的a，b∈∑+，可以使用A→aAa|bAb來產(chǎn)生{wAwT|w∈{a，b}+}

推廣到實際語言

{x | x=xT ， x Icirc; aring;}

{x | x=xT ， x Icirc; aring;+}

{xxT | x Icirc; aring;+}。

{xxT | x Icirc; aring;*}。

{x0xT | x Icirc; aring;+}

{xwxT | x， w Icirc; aring;+}。

{xxTw | x， w Icirc; aring;+}。

等等。

3自動機理論中的歸納和演繹

自動機理論教學(xué)活動中，也有很多歸納和演繹的應(yīng)用。

(1) 有限狀態(tài)自動機典型的余數(shù)問題

先從具體例子的討論入手，如：

構(gòu)造有限狀態(tài)自動機，識別{0，1}上的語言，該語言的每個字符串擋成二進制數(shù)時，代表的數(shù)字能整除5；

構(gòu)造有限狀態(tài)自動機，識別{0，1，2，4，5，6，7}上的語言，該語言的每個字符串擋成八進制數(shù)時，代表的數(shù)字能整除7；

構(gòu)造有限狀態(tài)自動機，識別{0，1，2，4，5，6，7，8，9}上的語言，該語言的每個字符串擋成十進制數(shù)時，代表的數(shù)字能整除3；

將此類問題歸納為：

構(gòu)造有限狀態(tài)自動機，識別X={x1，x2，x3，…xN-1}上的語言，該語言的每個字符串擋成二進制數(shù)(base=2)或八進制數(shù)(base=8)或十進制數(shù)(base=10)時，代表的數(shù)字能整除N。

分析：

將不同進制的數(shù)轉(zhuǎn)換為十進制數(shù)后，除以N的余數(shù)只能為0、1、2、3…和N-1，使用N個狀態(tài)分別代表已經(jīng)讀入的數(shù)字的和除以N的不同的余數(shù)的等價類：

q0：已經(jīng)讀入的數(shù)除以N，余數(shù)為0的輸入串的等價類；該類數(shù)為N*n+0;

q1：已經(jīng)讀入的數(shù)除以N，余數(shù)為1的輸入串的等價類；該類數(shù)為N*n+1;

q2：已經(jīng)讀入的數(shù)除以N，余數(shù)為2的輸入串的等價類；該類數(shù)為N*n+2;

…

qN-1：已經(jīng)讀入的數(shù)除以N，余數(shù)為N-1的輸入串的等價類；該類數(shù)為N*n+N-1;

注意：因為不能接收空串，所以，還需要一個開始狀態(tài)qS。

qS：在開始狀態(tài)讀入x時，進入對應(yīng)狀態(tài)qx；

qi：對應(yīng)已經(jīng)讀入的數(shù)w除以N，余數(shù)為i的輸入串的等價類；該類數(shù)為N*n+i;

當(dāng)前讀入的字符為x；則wx表示的十進制數(shù)為：

base*(N*n+i)+x

=N*base*n+base*i+x

該數(shù)對于N取余數(shù)就是base*i+x對于N的余數(shù)，若該余數(shù)為j，則相應(yīng)的狀態(tài)就應(yīng)該從qi變換為qj。

該應(yīng)用還可以推廣到任意進制和任意字母表的情況。

(2) 有限狀態(tài)自動機對于特定子串問題

先提出一般性原則，如構(gòu)造自動機，接收語言的每個句子必須包含特定的子串，課堂練習(xí)多個實際例子，反過來，再指導(dǎo)學(xué)生總結(jié)出更一般的規(guī)律，在此基礎(chǔ)上，推廣到另一類問題的解決，如構(gòu)造自動機，接收語言的每個句子必須不包含特定子串；接收語言的每個句子必須以特定子串開始或結(jié)束或必須在特定位置，等等。

實例1：構(gòu)造有限狀態(tài)自動機M，識別{0，1}上的語言L={x000}U{x001}，其中 x∈{0，1}*。

得到圖1所示的有限狀態(tài)自動機。

(3) 自動機類比和推廣

圖靈機的構(gòu)造設(shè)計到許多的技術(shù)，如存儲技術(shù)、移動技術(shù)查子程序技術(shù)等，設(shè)計了思考練習(xí)，討論是否可以將圖靈機的各種構(gòu)造技術(shù)應(yīng)用到有限狀態(tài)自動機或下推自動機的構(gòu)造中，開闊了學(xué)生的視野，活躍了學(xué)生的思想，得到某些教材里沒有的知識。也使學(xué)生掌握了類比和推廣的思維方法。

有限狀態(tài)自動機

實例2：使用存儲技術(shù)，構(gòu)造有限狀態(tài)接收機，輸入字母表為{a，b，c}，要求M接收語言L：該語言的每個字符串的第一個符號在該串中僅僅出現(xiàn)一次。

要求第一個符號僅僅出現(xiàn)一次，那么，有限狀態(tài)接收機可以“記住”輸入帶上的第一個符號(a或b或者c)，在掃描輸入帶上的其他符號時，與第一個符號進行比較，如果兩個符號相同，則拒絕并停機；如果輸入帶上的其他符號與第一個符號都不相同，則接收該字符串。

使用二元組表示單個狀態(tài)，其中第一個分量仍然表示原來的狀態(tài)；第二個分量是輸入帶上的第一個符號。[q，a]、[q，b]和[q，c]分別代表輸入帶上的字符串的第一個符號為a、b和c的狀態(tài)。

FA=(Q，∑， start，δ，F(xiàn))

其中，Q={start，[q，a]，[q，b]，[q，c]}，∑={a，b，c}

F={[q，a]，[q，b]，[q，c]

狀態(tài)轉(zhuǎn)換函數(shù)為δ

(1) δ(start，a)= [q，a]

δ(start，b)= [q，b]

δ(start，c)= [q，c]

(2) δ([q，a]，b)=[q，a]

δ([q，a]，c)=[q，a]

(3) δ([q，b]，a)=[q，b]

δ([q，b]，c)=[q，b]

(4) δ([q，c]，a)=[q，c]

δ([q，c]，b)=[q，c]

使用二元組[q，a]代表輸入帶上的字符串的第一個符號為a的狀態(tài)。有限狀態(tài)自動機的基本結(jié)構(gòu)和模型并沒有發(fā)生改變，但使用n元組表示一個狀態(tài)更為直觀和方便。

4總結(jié)

在形式語言和自動機理論課程的教學(xué)中，應(yīng)用歸納和演繹方法，合理地把握了理論的基本結(jié)構(gòu)，從形式語言與自動機的客觀事實出發(fā)，從特殊到一般地進行歸納概括，應(yīng)用舉一反三的間接推理的思維方法，使學(xué)生能夠獲得沒有在課堂上傳授的知識。運用規(guī)律進行邏輯思維，通過演繹推理解決問題，學(xué)生的計算思維能力得到大幅度的提高。歸納和演繹方法應(yīng)用于其他課程的學(xué)習(xí)中，可以有利地提高各門課程的教、學(xué)質(zhì)量。

參考文獻：

[1] 蔣宗禮，姜守旭. 形式語言與自動機理論[M]. 北京:清華大學(xué)出版社，2003.

[2] J.E. Hopcroft， R. Motwani， J.D. Ullman: Introduction to Automata Theory， Languages， and Computation[M]. Addison Wesley，2001.

[3] 張崇善. 課堂教學(xué)改革之理想選擇[EB]. 中國教育和科研計算機網(wǎng)，2007.

[4] 陳東. 計算機教學(xué)改革的一些嘗試[J]. 福建師范大學(xué)學(xué)報，20(3):98-100，2006.

[5] 蔡憲. 建構(gòu)S新型教學(xué)模式是教育技術(shù)的首要任務(wù)[J]. 電化教育研究，1999，16(5):19-21.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文