《《形式語言與自動機(jī)》課程教學(xué)大綱》由會員分享，可在線閱讀，更多相關(guān)《《形式語言與自動機(jī)》課程教學(xué)大綱（3頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、《形式語言與自動機(jī)》課程教學(xué)大綱 一、課程基本信息 中文名稱：形式語言與有限自動機(jī) 英文名稱：Formal Languages and Automata Theory 開課學(xué)院：計(jì)算機(jī)科學(xué)學(xué)院 課程編碼：S0812301 學(xué)分：2 總學(xué)時(shí)：36 適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)術(shù)碩士 修讀基礎(chǔ): 《離散數(shù)學(xué)》，《數(shù)字邏輯》 課程負(fù)責(zé)人：陳偉（教授） 主講教師：陳偉（教授） 二、課程目的任務(wù) 1.課程地位作用（課程在實(shí)現(xiàn)培養(yǎng)目標(biāo)中的地位作用） 《形式語言與自動機(jī)》是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)，本課程主要目的在于利用有限自動機(jī)與正則表達(dá)式的等價(jià)關(guān)系，通過表達(dá)式描述問題，

2、利用不同有限自動機(jī)類型實(shí)現(xiàn)解決方案，通過更一般化的上下文無關(guān)文法描述，利用下推自動機(jī)實(shí)現(xiàn)問題求解，培養(yǎng)學(xué)生描述問題、分析問題、尋求對策的創(chuàng)新思維模式，提高知識綜合應(yīng)用能力。 2.課程主要內(nèi)容（簡述：主要內(nèi)容、重點(diǎn)、難點(diǎn)等） 主要內(nèi)容包括：自動機(jī)理論發(fā)展歷史、有限自動機(jī)的描述特點(diǎn)與工作方式（重點(diǎn)、難點(diǎn)）、正則表達(dá)式與語言（重點(diǎn)、難點(diǎn)）、正則語言性質(zhì)、上下文無關(guān)文法與語言（重點(diǎn)、難點(diǎn)）、下推自動機(jī)、上下文無關(guān)語言的性質(zhì)（重點(diǎn)、難點(diǎn)）等。 3.學(xué)生應(yīng)達(dá)到的基本要求 本課程基本要求在于掌握有限自動機(jī)類型，有限自動機(jī)與正則表達(dá)式的等價(jià)關(guān)系、正則文法性質(zhì)、上下文無關(guān)文法與范

3、式、下推自動機(jī)與上下文無關(guān)語言性質(zhì)，重點(diǎn)在于研究應(yīng)用方法。 三、教學(xué)內(nèi)容與學(xué)時(shí)分配 （一）自動機(jī)：方法與體驗(yàn)（2學(xué)時(shí)） 主要內(nèi)容： 為什么研究自動機(jī)理論，自動機(jī)理論發(fā)展歷史，預(yù)備知識：字母表、串、語言、問題，主要命題證明方式。 重點(diǎn)：預(yù)備知識 （二）有限自動機(jī)（6學(xué)時(shí)） 主要內(nèi)容： 有限自動機(jī)的非形式化描述，確定型有限自動機(jī)、非確定型有限自動機(jī)、含空轉(zhuǎn)移有限自動機(jī)的描述特點(diǎn)與工作方式，三類自動機(jī)的等價(jià)轉(zhuǎn)換方式，子集構(gòu)造、空閉包概念，自動機(jī)的應(yīng)用。 重點(diǎn)：有限自動機(jī)的描述特點(diǎn)與工作方式 （三）正則表達(dá)式與語言（6學(xué)時(shí)） 主要內(nèi)容： 正則表達(dá)式的定義，自動機(jī)FA與正則式

4、RE的等價(jià)性及效驗(yàn)，RE代數(shù)規(guī)則及測試正則式RE的應(yīng)用。 重點(diǎn)：自動機(jī)FA與正則式RE的等價(jià)性 （四）正則語言性質(zhì)（6學(xué)時(shí)） 主要內(nèi)容： 證明語言的非正則性，泵引理，正則語言的閉合性（閉合算子），正則語言的判定性（測試正則語言的空或成員）、自動機(jī)的狀態(tài)等價(jià)與自動機(jī)最小化。 重點(diǎn)：正則語言的閉合性與自動機(jī)最小化 （五）上下文無關(guān)文法與語言（6學(xué)時(shí)） 主要內(nèi)容： 上下文無關(guān)文法的定義，文法推導(dǎo)過程，上下文無關(guān)文法的語言，語法分析樹和推導(dǎo)的等價(jià)性，語法分析器及其它上下文無關(guān)文法應(yīng)用，語法和語言中的歧義性及消除方法。 重點(diǎn)：語法分析樹和推導(dǎo)的等價(jià)性 （六）下推自動機(jī)（6學(xué)時(shí)） 主

5、要內(nèi)容： 下推自動機(jī)的定義，下推自動機(jī)的語言，下推自動機(jī)與上下文無關(guān)文法的等價(jià)性，確定型下推自動機(jī)定義與正則語言。 重點(diǎn)：下推自動機(jī)的工作方式與應(yīng)用 （七）上下文無關(guān)語言的性質(zhì)（4學(xué)時(shí)） 主要內(nèi)容： 上下文無關(guān)文法的范式，上下文無關(guān)語言的泵引理，上下文無關(guān)語言的閉合性，上下文無關(guān)語言的判定性。 重點(diǎn)：上下文無關(guān)語言的閉合性 四、考核方式與成績評定 1.考核方式：（筆試、論文、口試等） 要求平時(shí)認(rèn)真聽課，完成四則運(yùn)算計(jì)算器表達(dá)式的文法描述及解釋執(zhí)行的大作業(yè)。 2.成績評定辦法：（平時(shí)成績、期末考試成績……等比例） 論文撰寫（70％） 專題討論和答辯（30％）

6、 五、教材及主要參考書目 (一)教材 [1] John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman，Introduction to Automata Theory, Languages and Computation, 2nd edition，Addison Wesley，機(jī)械工業(yè)出版社，2004 (二)參考書 [1] 蔣宗禮、姜守旭，形式語言與自動機(jī)理論，清華大學(xué)出版社，2003年1月 [2] 蔣宗禮編著，形式語言與自動機(jī)理論教學(xué)參考書，清華大學(xué)出版社，2003年8月 [3] J. Hopcroft & J. Ullman, 自動機(jī)理論、語言和計(jì)算導(dǎo)引，徐美瑞譯，科學(xué)出版社，1990 六：其他需要說明的問題 大綱執(zhí)筆人：陳偉 大綱審批機(jī)構(gòu)： 計(jì)算機(jī)科學(xué)學(xué)院教授委員會 2015年 8月 25日