形式語(yǔ)言與自動(dòng)機(jī)課程教學(xué)大綱課程基本信息中文名稱形式

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

2、無(wú)關(guān)文法描述，利用下推自動(dòng)機(jī)實(shí)現(xiàn)問(wèn)題求解，培養(yǎng)學(xué) 生描述問(wèn)題、分析問(wèn)題、尋求對(duì)策的創(chuàng)新思維模式，提高知識(shí)綜合應(yīng)用能力。2. 課程主要內(nèi)容簡(jiǎn)述：主要內(nèi)容、重點(diǎn)、難點(diǎn)等 主要內(nèi)容包括：自動(dòng)機(jī)理論開(kāi)展歷史、有限自動(dòng)機(jī)的描述特點(diǎn)與工作方式重點(diǎn)、 難點(diǎn) 、正那么表達(dá)式與語(yǔ)言 重點(diǎn)、 難點(diǎn) 、正那么語(yǔ)言性質(zhì)、 上下文無(wú)關(guān)文法與語(yǔ)言 點(diǎn)、難點(diǎn)、下推自動(dòng)機(jī)、上下文無(wú)關(guān)語(yǔ)言的性質(zhì)重點(diǎn)、難點(diǎn)等。3. 學(xué)生應(yīng)到達(dá)的根本要求 本課程根本要求在于掌握有限自動(dòng)機(jī)類型，有限自動(dòng)機(jī)與正那么表達(dá)式的等價(jià)關(guān)系、 正那么文法性質(zhì)、上下文無(wú)關(guān)文法與范式、下推自動(dòng)機(jī)與上下文無(wú)關(guān)語(yǔ)言性質(zhì)，重點(diǎn)在于 研究應(yīng)用方法。三、教學(xué)內(nèi)容與學(xué)時(shí)分配一

3、自動(dòng)機(jī)：方法與體驗(yàn) 2 學(xué)時(shí)主要內(nèi)容：為什么研究自動(dòng)機(jī)理論， 自動(dòng)機(jī)理論開(kāi)展歷史，預(yù)備知識(shí)：字母表、串、語(yǔ)言、 問(wèn)題，主要命題證明方式。重點(diǎn)：預(yù)備知識(shí)二有限自動(dòng)機(jī) 6 學(xué)時(shí)主要內(nèi)容：有限自動(dòng)機(jī)的非形式化描述，確定型有限自動(dòng)機(jī)、非確定型有限自動(dòng)機(jī)、含空 轉(zhuǎn)移有限自動(dòng)機(jī)的描述特點(diǎn)與工作方式，三類自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換方式，子集構(gòu)造、 空閉包概念，自動(dòng)機(jī)的應(yīng)用。重點(diǎn)：有限自動(dòng)機(jī)的描述特點(diǎn)與工作方式三正那么表達(dá)式與語(yǔ)言 6 學(xué)時(shí)主要內(nèi)容：正那么表達(dá)式的定義，自動(dòng)機(jī) FA與正那么式RE的等價(jià)性及效驗(yàn)，RE代數(shù)規(guī)那么及測(cè)試 正那么式 RE 的應(yīng)用。重點(diǎn)：自動(dòng)機(jī) FA 與正那么式 RE 的等價(jià)性四正那么語(yǔ)言性質(zhì)

4、6 學(xué)時(shí)主要內(nèi)容： 證明語(yǔ)言的非正那么性，泵引理，正那么語(yǔ)言的閉合性閉合算子，正那么語(yǔ)言的判定 性測(cè)試正那么語(yǔ)言的空或成員、自動(dòng)機(jī)的狀態(tài)等價(jià)與自動(dòng)機(jī)最小化。重點(diǎn)：正那么語(yǔ)言的閉合性與自動(dòng)機(jī)最小化五上下文無(wú)關(guān)文法與語(yǔ)言 6 學(xué)時(shí)主要內(nèi)容： 上下文無(wú)關(guān)文法的定義，文法推導(dǎo)過(guò)程，上下文無(wú)關(guān)文法的語(yǔ)言，語(yǔ)法分析樹(shù)和推 導(dǎo)的等價(jià)性， 語(yǔ)法分析器及其它上下文無(wú)關(guān)文法應(yīng)用，語(yǔ)法和語(yǔ)言中的歧義性及消除方 法。重點(diǎn)：語(yǔ)法分析樹(shù)和推導(dǎo)的等價(jià)性六下推自動(dòng)機(jī) 6 學(xué)時(shí)主要內(nèi)容：下推自動(dòng)機(jī)的定義，下推自動(dòng)機(jī)的語(yǔ)言，下推自動(dòng)機(jī)與上下文無(wú)關(guān)文法的等價(jià)性， 確定型下推自動(dòng)機(jī)定義與正那么語(yǔ)言。重點(diǎn)：下推自動(dòng)機(jī)的工作方式與應(yīng)用七

5、上下文無(wú)關(guān)語(yǔ)言的性質(zhì) 4 學(xué)時(shí)主要內(nèi)容：上下文無(wú)關(guān)文法的范式，上下文無(wú)關(guān)語(yǔ)言的泵引理，上下文無(wú)關(guān)語(yǔ)言的閉合性，上 文無(wú)關(guān)語(yǔ)言的判定性。重點(diǎn)：上下文無(wú)關(guān)語(yǔ)言的閉合性 四、考核方式與成績(jī)?cè)u(píng)定1.考核方式：筆試、論文、口試等 要求平時(shí)認(rèn)真聽(tīng)課，完成四那么運(yùn)算計(jì)算器表達(dá)式的文法描述及解釋執(zhí)行的大作業(yè)。2成績(jī)?cè)u(píng)定方法：平時(shí)成績(jī)、期末考試成績(jī)等比例論文撰寫 70 專題討論和辯論 30 五、教材及主要參考書(shū)目一教材1 John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman ， Introduction to Automata Theory, Languages and Computation, 2nd edition ，Addison Wesley ，機(jī)械工業(yè)出版社， 2004二參考書(shū)1 蔣宗禮、姜守旭，形式語(yǔ)言與自動(dòng)機(jī)理論，清華大學(xué)出版社， 2003 年 1 月2 蔣宗禮編著，形式語(yǔ)言與自動(dòng)機(jī)理論教學(xué)參考書(shū)，清華大學(xué)出版社， 2003 年 8 月3 J. Hopcroft & J. Ullman